[백준 2579] 계단 오르기

 

예제로 풀이해보겠다.

 

	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]
점수	10	20	15	25	10	20

점수 배열이다.

 

 

 

	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]
첫번째 경우	10	20	15	25	10	20
두번째 경우	10	20	15	25	10	20

 

마지막 계단은 반드시 밟아야 하므로 뒤에서 되돌아오는 식으로 점화식을 구현해야 한다.

 

dp[5] = dp[2] + a[4] + a[5];

dp[5] = dp[3] + a[5];

중 큰 값을 선택한다. 두번째 경우에서 a[1] 을 썼는지 a[2] 를 썼는지 확인할 수 없으므로 dp[3]만 사용한다.

 

식으로 나타내면

---

dp[i] = max(dp[i-3] + a[i-1] + a[i], dp[i-2] + a[i]);

---

가 되겠다.

 

 

 

이런식으로 구현하면 dp[0], dp[1], dp[2] 는 비어있게 되는데 피보나치 수열처럼 앞쪽은 미리 채워줘야 한다.

 

 

	dp[0]	dp[1]	dp[2]
점수	10	max(10, 10 + 20)	max(10 + 15, 20 + 15)

 

dp[0] 는 a[0] 값을 끌어온다.

dp[1] 은 a[0], a[0] + a[1] 중 큰 값을 사용한다.

dp[2] 는 a[0] + a[2], a[1] + a[2] 중 큰 값을 사용한다. (a[0] + a[1] 는 a[2] 에서 사용할 수 없다.)

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[] = new int[300];
        int dp[] = new int[300];
        
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        dp[0] = a[0];
        dp[1] = max(a[0], a[0] + a[1]);
        dp[2] = max(a[0] + a[2], a[1] + a[2]);
        for(int i=3; i<300; i++)
            dp[i] = max(dp[i-3] + a[i-1] + a[i], dp[i-2] + a[i]);
        
        System.out.println(dp[n-1]);
        sc.close();
    }
    
    public static int max(int a, int b) {
        return a > b ? a : b;
    }
}