백준 - 2579번: 계단 오르기 (C++)

Pixabay로부터 입수된 Laurent Verdier님의 이미지 입니다.

 

---

 

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

2579번: 계단 오르기

 

 이번 문제는 주어진 조건에 따라 계단을 끝까지 올라갔을 때, 점수의 최대값을 구하는 문제이다. 이 문제는 2년 전에 처음 접했다가 다른 분의 풀이를 보고 그대로 적용했었던 문제라 다시 한 번 복습할 겸 풀어 보았다.

 처음에는 재귀함수처럼 문제를 풀었지만 제대로 풀리지가 않았다. 그래서 다시 한 번 생각해보니 계단을 처음부터 올라가는 문제, 즉 처음부터 점진적으로 답을 찾아가는 문제라는 것을 깨달았다. 그래서 반복문 형식으로 문제를 풀었다.

 

 우선, 첫 번째 계단부터 세 번째 계단까지는 별도의 과정 없이 각 계단의 최대 점수를 구할 수 있다.

• 첫 번째 계단까지의 최대 점수는 첫 번째 계단의 점수이다.
• 두 번째 계단까지의 최대 점수는 첫 번째 + 두 번째 계단의 점수 합과 두 번째 계단만의 점수의 합(두 계단 올라가는 경우) 중, 더 큰 값이다.
• 세 번째 계단까지의 최대 점수는 첫 번째 + 세 번째 계단 점수 합과 두 번째 + 세 번째 계단의 점수 합 중 더 큰 값이다. 

그리고 네 번째 계단부터, 그 계단의 최대 점수는 다음과 같다. n번째 계단에서의 최대 점수를 dp[n]이라고 할 때, 점화식은 다음과 같다.

 

dp[n] = max(dp[n - 2] + 계단점수[n], dp[n - 3] + 계단점수[n - 1] + 계단점수[n])

 

우선, max의 첫 번째 인자에 해당하는 경우는 n - 2번째 계단에서 두 계단을 올라가는 경우이다. 그리고 두 번째 인자에 해당하는 경우는 n - 3번째 계단에서 n - 1번째 계단으로 두 계단 오른 후, n번째 계단으로 한 계단 올라가는 경우이다. 이를 반복문을 이용해 주어진 계단 개수까지 반복문을 진행한다.

 

#include <iostream>
#define MAX 301

using namespace std;

int stairNum;
int stair[MAX];
int dp[MAX];

int main()
{
    ios_base::sync_with_stdio(0);
	std::cout.tie(NULL);    
	std::cin.tie(NULL);

    cin >> stairNum;

    for (int i = 1; i <= stairNum; ++i)
        cin >> stair[i];

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

    for (int stairIdx = 4; stairIdx <= stairNum; ++stairIdx)
        dp[stairIdx] = max(dp[stairIdx - 2] + stair[stairIdx], dp[stairIdx - 3] + stair[stairIdx - 1] + stair[stairIdx]);

    cout << dp[stairNum] << endl;

    return 0;
}