[백준 2579][C++] 계단 오르기 (Silver 3)

[문제보기]

 2579. 계단 오르기

2579번: 계단 오르기

 

[풀이과정]

일단 이 문제를 보고 드는 생각은 dp로 풀어야겠다고 생각을 했다. 왜냐하면 결국에는 마지막 계단을 밟았을 때 제일 

높은 점수를 찾는 문제이고, 각각 계단을 밟을 수 있는 경우에 대해 제일 높은 값으로 갱신을 해주면 되겠다고 

생각했기 때문이다. 

 

문제에서 제시하는 3가지 조건이 있다. 3번째 조건은 신경을 안 써줘도 되지만, 1,2 번째에 대한 조건을 dp의 점화식을 

세울 때 신경을 써줘야 되는 부분이다. 

첫 번째 조건을 정리를 하면, 계단은 1칸 혹은 2칸씩 오를 수가 있다. 따라서 현재 서 있는 계단을 오를 수 있는 경우는

두 가지가 된다.(1칸을 뛰어서 오는 경우, 2칸을 뛰어서 오는 경우)

그리고 두 번째 조건을 적용을 한다면, 현재 계단이 n번째 계단일 때, 이 계단으로 올 수 있는 경우는,

[n-3]번째 계단에서 [n-1]번째 계단을 밟고 [n]번째 계단으로 오는 경우([n-2]번째 계단을 뛰어넘었다)와

[n-2]번째 계단에서 [n]번째 계단으로 바로 오는 경우가 된다.

예를 들어 [4]번째 계단으로 오는 경우는

[1]번째 계단에서 시작(dp[1)하여 [3]번째 계단을 밟고(+step[3]) [4]번째 계단으로 도착(+step[4])하는 경우 vs

[2]번째 계단에서 시작{dp[2])하여 [4]번째 계단으로 도착(+step[4])하는 경우가 된다.

 

이를 점화식으로 나타내면

dp[n] = max(dp[n-3] + step[n-1] + step[n] , dp[n-2]+step[n]);

가 된다.

[소스코드]

#include <iostream>
using namespace std;
int step[301] = {0};
int dp[301] = {0};

int main(){
    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> step[i];
    }

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

 

[해결 과정 중 실수한 부분]

처음에는 좀 어렵게 생각을 했다. 현재의 계단으로 올 수 있는 경우를 생각하려고, dp를 2차원 배열로 만들어

한 칸을 뛴 경우, 두 칸을 뛴 경우로 나눠서 생각을 했다. 

하다 보다가 점화식이 너무 복잡하게 나와 지우고 다시 생각을 해봤고, dp를 1차원으로 만들어서

생각을 해봤다.