[동적 계획법 1] [C++] 2579번. 계단 오르기

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

---

해결 방법

dp 문제이므로 점화식을 찾아야한다.

도착지점에 갈 수 있는 방법은 어떻게 될까? 두 가지로 나눌 수 있다.

 

i) 전 계단을 밟고 도착 지점을 밟는 경우

ii) 전전 계단을 밟고 도착 지점을 밟는 경우

 

이렇게 두 가지로 나눌 수 있는데 주의할 점은 연속된 3개의 계단은 밟을 수 없다는 것이다.

 

즉, i) 에서 전 계단을 밟기 이전에 전전 계단을 밟을 수 없고, 무조건 전전전 계단을 밟아야한다는 것이다.

 

따라서 이 조건을 점화식으로 나타내면

i) 전전전 계단의 최대값 + 전 계단 + 도착 계단 = dp[i-3] + stair[i-1] + stair[i]

ii) 전전 계단의 최대값 + 도착 계단 = dp[i-2] + stair[i]

위와 같이 나타낼 수 있다.

 

 

해결 과정

위의 점화식을 반복문을 통해 탐색하면 된다. 여기서 한 가지 더 주의할 점이 있다.

점화식을 살펴보면 dp[i-3], dp[i-2] 이므로 반복문의 시작 index 값을 i≥3 으로 잡아줘야 한다는 것이다.

따라서 dp[0], dp[1], dp[2]를 미리 선언해놓을 필요가 있다.

 

해당 계단까지의 최대 값을 저장해놓은 배열이 dp라고 할 때 아래와 같이 나타낼 수 있다.

dp[0] = stair[0]

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

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

여기서 max함수는 최대 값을 return하는 함수이다.

 

최종 코드는

 

#include <iostream>
using namespace std;


int max(int a, int b){
    return a > b ? a : b;
}

int main(){
    int n;
    int stair[300], dp[300];
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> stair[i];
    }
    
    dp[0] = stair[0];
    dp[1] = max(stair[1], stair[0] + stair[1]);
    dp[2] = max(stair[0] + stair[2], stair[1] + stair[2]);
    
    for(int i = 3; i < n; i++){
        dp[i] = max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]);
    }
    
    cout << dp[n-1];
    
    return 0;
}