다이나믹프로그래밍- 계단 오르기(백준2579번)

1.다이나믹 프로그래밍 - 계단 오르기 (백준 2579번)

---

---

2.다이나믹 프로그래밍을 이용한 풀이

---

package dynamicProgramming;
 
import java.util.Scanner;
 
public class Baejoon2579UpStair {
    static int[] stairArr;
    static int[] memo=new int[301];
    static int count=1;
    static void initMemo(int[] memo) {
        for(int i=0;i<memo.length;i++) {
            memo[i]=-1;
        }
        memo[0]=0;
        memo[1]=stairArr[1];
        memo[2]=stairArr[1]+stairArr[2];
    }
    static int upStair(int n) {
        if(memo[n]!=-1) {
            return memo[n];
        }
        memo[n]=Math.max(upStair(n-3)+stairArr[n-1]+stairArr[n],upStair(n-2)+stairArr[n]);
        return memo[n];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        
        int n=sc.nextInt();
        stairArr=new int[n+1];
        
        for(int i=1;i<n+1;i++) {
            stairArr[i]=sc.nextInt();
        }
        initMemo(memo);
        System.out.println(upStair(n));
    }
 
}
 

이 문제 풀이의 핵심은 각 계단을 마지막 계단으로 보는 것입니다. 예를 들어 가장 마지막 계단을 오르는 경우의 수는 이전 계단을 밟는 경우와 전전계단을 밟는 경우 총 2가지입니다. 여기에서 이전 계단을 밟는 경우에서 upStair(n-3) 재귀호출까지 더해주는 이유는 3번 연속된 계단을 밟을 수 없기 때문입니다. 이 두가지 경우 중에서 큰수를 Math 클래스의 max 메소드를 이용해서 구합니다. 그래서 이 두가지의 경우로 재귀호출을 통해 다시 함수에 들어가게 되면 그 계단을 다시 마지막 계단으로 보고 다시 위의 두 가지 경우로 나뉘어서 재귀 호출을 반복하게 됩니다. 이 과정을 반복하다가 초기화된 값까지 다다르게 되면 모든 값이 메모된 값을 이용하여 총합을 구할 수 있게 됩니다. 여기에서 2번째 계단을 밟은 가장 큰 경우의 수는 1번째 계단을 밟는 경우이므로 stairArr[1]+stairArr[2] 를 통해 초기화를 해줍니다.