[C++] 백준 알고리즘 2579 계단 오르기 (동적 계획법)

2579번: 계단 오르기 (acmicpc.net)

2579번: 계단 오르기

동적 계획법 (dynamic programming) 이란 무엇일까?

바로 현재 값을 구할 때, 과거에 구한 값을 활용하는 알고리즘이다.

 

예를 들어 내가 한 노드에 있는데 이 노드로 올 수 있는 길은 두 갈래 라고 하자.

왼쪽 노드에서 와야 최단 경로인지, 오른쪽 노드에서 와야 최단 경로인지 구해야한다.

출발지에서 왼쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 3의 비용으로 왼쪽 노드까지 갈 수 있다.

그리고 출발지에서 오른쪽 노드까지 가는 최소 비용의 합을 dp 배열에 저장한다. 위 그래프에서는 4의 비용으로 오른쪽 노드까지 갈 수 있다.

 

그리고 왼쪽 노드의 dp 값 + 왼쪽 노드에서 도착지까지 올 때의 비용 = 3 + 10 = 13 ,

오른쪽 노드의 dp + 오른쪽 노드에서 도착지까지 올 때의 비용 = 4 + 8 = 12

... 을 계산해서 더 적은 비용을 dp 값에 갱신해주면 최단 경로를 구할 수 있다.

최단 경로는 12가 되고, 도착 노드의 dp 값은 12가 된다.

 

왼쪽 노드까지 가는 최단 경로, 오른쪽 노드까지 가는 최단 경로도 이런식으로 dp를 이용해 구한다면

원하는 지점까지의 최단 경로를 구할 수 있다.

이때 점화식이 중요하다. 계단 오르기 문제를 풀어보자.

---

계단 오르기는 연속된 세칸의 계단을 밟지 않고 도착할 수 있는 최대 비용을 구하는 문제이다.

계단을 오르면서 누적되는 점수 합의 최댓값을 dp 배열에 저장해준다.

 

현재 계단까지 오기 위해, 계단을 2칸 건너 뛰어야지 더 큰 값으로 도착할 수 있었는지,

아니면 1칸을 건너 뛰어야지 더 큰 값으로 도착할 수 있었는지 계산한다.

 

score에는 현재 점수 값이 있고, dp 배열에는 해당 계단까지 오기 위한 최대 누적 합을 저장한다.

 

#include<iostream>
#include<vector>

using namespace std;

int maxScore(int n, vector<int> score){
    vector<int>dp(n+1, 0);
    dp[1]=score[1]; //첫 번째 계단 점수 저장
    dp[2]=score[1]+score[2];//dp[i-2]를 접근해야 하므로 dp[2] 값 미리 저장
    // 두 번째 계단 오르는 경우는 첫 번째 계단을 밟고 한칸 올라가는 방법 밖에 없음

    //dp[i-3]을 접근하는데 dp[3]을 저장하지 않은 이유?
    //문제가 되는 경우는 i-3을 접근하는데 i=3 일 때, 우리가 사용하지 않을 dp[0]을 접근하는 경우이다.
    //하지만 dp[0]=0이고, dp[0]+score[2] = score[2] 가 된다.
    //즉 3번째 계단을 오를 때는 score[2] + score[3] 이 된다.
    //근데 이때 (score[2] = 1, 2 번째 계단을 오르는거고 score[3] = 3 번째 계단을 오르는 것이므로) 1, 2, 3 계단 연속 3번 밟게 되는게 아닌가?
    // -> 아니다. 연속 3개인지 카운트 할 때 첫 번째 계단은 포함하지 않는다고 명시됨

    for(int i=3; i<=n; i++){
        // (이번에 2칸을 오르거나, 전에 2칸 오른 상태 + 이번에 1칸 오르기) 한 것 중 최댓값 + 현재 점수
        //왜냐하면 dp[i-3] + score[i-1]를 하지 않으면 한칸씩 연달아 3번 오르게 될 수 있음
        //따라서 한칸을 오르려면 전전에 두칸 올라야만 [ 2칸 -> 1칸 -> 1칸 ] 이 되고, 연속 1칸씩 3번 오르지 않게 됨
        dp[i] = max(dp[i-2],dp[i-3] + score[i-1]) + score[i];
    }
    return dp[n];
}

int main(){
    int n;
    cin>>n;

    vector<int> score(n+1,0); //n+1인 이유? 인덱스 1부터 시작하기 위해서
    //인덱스 1부터 시작하는 이유? [i-1]를 접근해야하기 때문
    for (int i=1; i<=n; i++)
        cin>>score[i];

    cout<<maxScore(n, score)<<'\n';

}