[백준] 2579번: 계단 오르기

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

문제

알고리즘 접근 방법

DP를 이용한다.

계단 점수를 저장하는 배열 stair과 얻을 수 있는 총 점수의 최댓값을 저장하는 배열 dp가 존재한다.

먼저 문제를 읽어보면, 아래와 같은 조건이 있다.

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

dp 배열을 구해나가보겠다.

• n=1
  dp[1] = stair[1]

• n=2
  dp[2] = stair[1] + stair[2]

• n=3
  여기서부터 DP를 이용한다.
  dp[3] 은 1번계단 + 2 칸 올라간 3번 계단 [0 1 _ 3] or 2칸 뛰어 올라간 2번계단 + 3번계단 [ 0 _ 2 3 ] 중 최댓값이다.

• n=4
  dp[4] 는 [ ~ 2 _ 4] or [ ~1 _ 3 4] 이다.

이렇게 점화식을 세우면
dp[n] = max(dp[n-2]+stair[n], dp[n-3]+stair[n-1]+stair[n])
이 된다.

마지막 계단을 반드시 밟아야 한다는 점에 대해 유의한다.

풀이

#include <iostream>
#include <algorithm>

using namespace std;

int main(){
    int n, a, b, c; 

    cin >> n;

    int stair[n+1] = {0,};

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

    int dp[n+1] = {0,};

    dp[0] = 0; // 시작점
    dp[1] = stair[1];
    dp[2] = stair[1] + stair[2];


    for(int i=3; i<=n; i++){

        a = dp[i-2]+stair[i];
        b = dp[i-3]+stair[i-1]+stair[i];

        dp[i] = max(a, b);
        
    }

    cout << dp[n] << endl;

    return 0;
}

정리

포도주 문제랑 비슷했는데 자꾸 생각이 어렵게 되는 .. 문제.. 어케 고치ㅣ죠?ㅠㅠ

💡 참고 포스팅

yabmoons님 블로그