(2579)(DP) 백준 계단오르기

https://www.acmicpc.net/problem/2579

풀이

---

계단을 차근차근 올라 마지막 계단(꼭 거쳐야하는 계단)까지 밟았던 계단의 합이 최대값이 나오게 하는 알고리즘을 짜야한다.

단 조건이 있는데

1. 계단은 한번에 1칸 or 2칸을 올라갈 수 있다.

2. 연속된 세 개의 계단을 모두 밟으면 안된다.

3. 마지막 도착 계단은 반드시 밟아야한다.

1, 2, 3의 조건을 모두 조합해서 최대합 dp를 구하는 식을 나타내보면

---

arr[1] arr [2]  /중략/  arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n]     <<- n개의 계단을 만들었다고 치면 계단 마지막 쯤은 이런식으로 생겼을 것이다. 

n의 계단을 꼭 밟는다는 조건을 충족하기 위해서는 

1. arr[n-3]  ,  arr[n-1]  ,  arr[n] 을 차례로 밟는 경우

2. arr[n-2]    arr[n] 을 차례로 밟는 경우

위의 두가지 경우가 가장 최소한의 경우라고 할 수 있다. 위의 경우는 세가지 조건에 모두 위배되지 않고

두 식으로 충분히 모든 경우의 수를 계산할 수 있다는 것을 노트에 조금만 적어서 생각해보면 알 수 있다. 

그래서 down-top방식으로 dp배열에 누적합을 구해 비교 저장하는 식

---

1. arr[n-3]  ,  arr[n-1]  ,  arr[n] 을 차례로 밟는 경우를 누적하는 식으로 응용

dp[i] = dp[i - 3] + arr[i] + arr[i - 1];

2. arr[n-2]    arr[n] 을 차례로 밟는 경우

dp[i] = dp[i - 2] + arr[i];

비교해서 저장한다.

-->>

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

#include <stdio.h>
 
#define max(a,b) a>b ? a:b
 
 
int main() {
    int arr[301] = { 0 };
    int dp[301] = { 0 };
    int N;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    dp[1] = arr[1];
    dp[2] = dp[1] + arr[2];
    for (int i = 3; i <= N; i++) {
        dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1]);
    }
 
    printf("%d", dp[N]);
 
    return 0;
    
}