백준 2579 계단 오르기

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

2579번: 계단 오르기

 

 

 

EXPLANATION

 

계단 오르는 데는 다음과 같은 규칙이 있다.

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

 

문제 조건에 따르면 i번째 이전의 계단에서 i번째 계단으로 가려면 i - 1번째 또는 i - 2번째 계단을 거쳐가는 방법밖에 없다.

즉, i번째 계단의 최대 누적 점수를 구하기 위해서 우리는 무조건 i - 1번째 계단이나 i - 2번째 계단을 이용해야 한다.

 

 

i 번째 계단이 가지는 점수를 stair[i]라고 하고,

i번째 계단에서 얻을 수 있는 최대 누적 점수를 dp[i]라고 하자.

 

i - 1 또는 i - 2번째 계단을 이용했을 때 구해지는 각 각의 i번째 계단의 최대 누적 점수(dp[i]후보)를 구하고,

그 중에서 가장 큰 값이 dp[i]이다.

 

 

i -1번째 계단에서 i번째 계단으로 갈 수 있으므로

dp[i - 1]에 stair[i]를 더하면 dp[i] 후보가 될거 같다.

그런데, 여기에는 오류가 있다.

dp[i - 1]이 stair[i - 2]을 이용해서 구해졌다면

dp[i - 1] + stair[i] = dp[i](후보)의 경우 3개의 계단을 연속으로 이용하기 때문에 조건에 어긋난다.

 

( 아직 i - 1번째나 i - 2번째 계단을 이용해서 dp[i] 후보를 구할 수 있는 경우 중 어느 경우도 구하지 못했다. )

 

 

그러면, i -2번째 계단에서 i번째 계단으로 갈 수 있으므로

dp[i - 2]를 이용해서 dp[i]를 구할 수 있을 거 같다.

이 경우 i - 2번째 계단과 i번째 계단은 2칸 뛰어져 있기 때문에 dp[i - 2]가 이미 stair[i - 2], stair[i - 3]를 이용해서 구해져 있더라도 상관없이 3계단을 연속하지 않기 때문에

dp[i - 2] + stair[i] = dp[i](후보)로 나타낼 수 있다.

 

(i - 2번째 계단을 이용하는 경우는 구했다. 여전히 i - 1번째 계단을 이용하는 경우가 남았다. )

 

 

dp[i - 3]을 이용해서 dp[i]를 구할 수 있을까?

한 번에 최대 2칸 뛸 수 있기 때문에 i - 3번째에서 i번째로 뛸 방법이 없다.

그런데 우리는 i - 1번째를 통해서 i번째로 갈 수 있음에도 아직 stair[i  - 1]을 통해서 dp[i]를 구한 적이 없다.

i - 3번째에서  i - 1번째로 두 칸 뛰어서 간 후 i번째로 가면 3번 연속하지 않고 i번째로 갈 수 있으므로 

dp[i - 3] + stari[i - 1] +stair[i] = dp[i](후보)로 나타낼 수 있다.

 

( i - 1번째, i - 2번째 계단을 통해서 구할 수 있는 모든 dp[i] 후보를 구했다. 따라서 가능한 모든 경우의 dp[i] 후보가 구해졌다. )

 

 

그 다음, dp[i - 4],dp[i - 5],...,dp[0]들을 이용해서 dp[i] 후보를 구할 수 있을까?

본론부터 말하면 위에서 구한 경우들에 포함된다. 

위에 노란줄 쳐진 부분을 명심한 후 괄호쳐진 부분의 도움을 받으며 글을 읽었다면 직관적으로 이해할 수 있을 것이다. 

i - 4번째 보다 작거나 같은 index에서 i번째로 가려면 어쨌든 역시 i - 2번째나 i - 1번째를 거쳐가야 한다.

ex)

dp[i - 4]를 이용할 때,

i - 2번째를 거쳐가면 dp[i - 2]가 나타내는 경우에 포함되고

i - 1번째를 거쳐가면 dp[i - 3]이 나타내는 경우에 포함된다.

 

 

 

base 구하기:

i가 2, 1, 0 일때 dp[i - 3]은 음의 index를 가지므로

dp[0], dp[1], dp[2]를 구해야 한다.

dp[0] = stair[0]

dp[1] = stair[0] + stair[1]

dp[2] = max(stair[0], stair[1]) + stair[2] (3번 연속 못하므로)

 

 

 

점화식

dp[0] = stair[0]
dp[1] = stair[0] + stair[1]
dp[2] = max(stair[0], stair[1]) + stair[2]

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

 

 

 

CODE

#include <iostream>
using namespace std;

int main(void){
    int N;
    cin >> N;
    int stair[300] = {};
    int dp[300] = {};
    for(int i = 0; i < N; i++ ){
        cin >> stair[i];
    }
    dp[0] = stair[0];
    dp[1] = stair[0]+stair[1];
    dp[2] = max(stair[0], stair[1]) + stair[2];

    for(int i = 3; i < N; i++){
        dp[i] = max(dp[i-2], dp[i-3] + stair[i-1]) + stair[i];
    }
    cout << dp[N-1] << " ";
}