문제

최근 부족한 DP를 만회하기 위해 DP만 골라 푸는 중이다

백준 2579번 : 계단 오르기

코드

#include <bits/stdc++.h>

using namespace std;

int N;
int arr[304];
int dp[304];

int main()
{
    cin >> N;

    for (int i = 1; i <= N; i++)
    {
        cin >> 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 - 1] + arr[i]);
    }

    cout << dp[N];

    return 0;
}

풀이

우선 이 문제의 규칙은 다음과 같다

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

1번 규칙을 언뜻보고 max(dp[i-1] + arr[i], dp[i - 2] + arr[i]라고 생각할 수 있는데 2번 규칙때문에 그렇게 안된다

dp[i - 1] + arr[i]의 의미가 현재 계단에서 한 계단을 올라가는 의미인데 이것은 2번 규칙을 지켰는지 안지켰는지 모른다. 내가 arr[i-1]번 계단까지 1칸 씩 연속으로 2번 밟았으면 그 다음 계단을 밟으면 안 되기 때문임

그래서 dp[i - 2] + arr[i]를 고려해준다. i - 2번째 계단에서 두 계단을 오른거니까 2번 규칙은 아예 신경 안써도 됨

그럼 i번째 계단을 오를 수 있는 방법은 i-2번째 계단에서 두 계단을 오른 경우와 나머지 방법으로

i-3번째 계단에서 시작해서 i-3번째에서 두 계단을 오르고 i-1번째 계단에서 한 계단을 오르는 경우다

앞에서 봤던 경우랑 다르므로 잘 작동한다

점화식을 잘 생각하자