[코드업] 계단오르기 (C++)

---

계단 오르기

 

문제

이 문제는 일정한 점수가 쓰여있는 계단에서 마지막 계단까지 올라가는 문제로, 계단을 오를 때는 3가지 규칙이 존재한다.

1. 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

주어진 각 계단의 점수를 이용하여 얻을 수 있는 총 점수의 최대값을 구한다.

 

풀이

DP를 사용하여 각 계단 별 최대 점수를 구해 n번째 계단까지의 최대 점수를 구한다.

 

 

식을 세우기 전에 쉬운 이해를 돕기 위해 한글로 설명하겠다.

 

dp[n] (n 번째 계단까지의 최대 점수), stairs[n] (n 번째 계단의 점수) 일 때,

 

0 번째 계단까지의 최대 점수

• 0 번째 계단에 올라갔을 때

1 번째 계단까지의 최대 점수

• 0 번째 계단, 1 번째 계단에 올라갔을 때

2 번째 계단까지의 최대 점수

• 0 번째 계단, 2 번째 계단에 올라갔을 때
• 1 번째 계단, 2 번째 계단에 올라갔을 때
• 두가지의 경우의 수 중 최대 점수를 구한다.

3 ~ n 번째 계단까지의 최대 점수

• 두 칸 올라갔을 때
  • 올라간 현재 계단의 점수(stairs[n]) + 두 칸 전까지 계단을 올랐을 때 최대 점수 (dp[n-2])
• 한 칸씩 올라갈 때
  • 올라간 현재 계단의 점수(stairs[n]) + 한 칸 전 계단의 점수 (stairs[n-1]) + 세 칸 전까지 계단을 올랐을 때 최대 점수 (dp[n-3])

---

위의 내용을 바탕으로 점화식을 세운다면 아래와 같이 세울 수 있다.

 

dp[0] = stairs[0] 

dp[1] = stairs[0] + stairs[1] 

dp[2] = stairs[0] + stairs[2] or  stairs[1] + stairs[2] 

dp[n] = stairs[n] + dp[n-2] or stairs[n] + stairs[n-1] + dp[n-3]

 

해당 점화식을 바탕으로 이 문제를 풀이하면 된다.

 

반복문을 이용한 풀이

// 반복문으로 풀이
#include <iostream>
#include <cmath>
// https://codeup.kr/problem.php?id=4564
using namespace std;

int dp[301] = { 0, };
int stairs[301] = { 0, };
int n;

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> stairs[i];
    }
	
    // 0번 ~ 2번 계단의 최대 점수
    dp[0] = stairs[0];
    dp[1] = stairs[0] + stairs[1];
    dp[2] = max(stairs[0] + stairs[2], stairs[1] + stairs[2]);

    for (int i = 3; i < n; i++) {
	// 한번에 2칸 올라갔을 때, 연속적으로 2칸 올라갔을 때 중 최댓 값 dp 테이블에 저장
        dp[i] = max(stairs[i] + dp[i - 2], stairs[i] + stairs[i - 1] + dp[i - 3]);
    }

    cout << dp[n - 1] << endl;

    return 0;
}

 

재귀 함수를 이용한 풀이

// 재귀함수로 풀이
#include <iostream>
#include <cmath>

using namespace std;

int dp[301] = { 0, };
int stairs[301] = { 0, };
int n;

int MaxScore(int idx) {
    // 0번 ~ 2번 계단의 최대 점수
    if (idx == 0) return stairs[0];
    if (idx == 1) return stairs[0] + stairs[1];
    if (idx == 2) return max(stairs[0] + stairs[2], stairs[1] + stairs[2]);

    // 이미 구한 dp 테이블 값일 때 중복 계산을 방지
    if (dp[idx] != 0) return dp[idx];

    // 한번에 2칸 올라갔을 때, 연속적으로 2칸 올라갔을 때 중 최댓 값 dp 테이블에 저장
    dp[idx] = max(stairs[idx] + MaxScore(idx - 2), stairs[idx] + stairs[idx - 1] + MaxScore(idx - 3));
    return dp[idx];
}

int main() {
    cin >> n;

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

    cout << MaxScore(n - 1) << endl;

    return 0;
}

 

재귀 함수로 풀이했을 때,

6 10 20 15 25 10 20 이렇게 입력 받는 다면 최대 점수(dp[5])를 값을 구할 때 dp[4]의 값은 구하지 않는다.

6 10 20 15 25 10 20 입력

 

CodingTestPractice/CodeUp/재귀 함수/계단오르기.cpp at main · seungdo1234/CodingTestPractice

 

DP에 대한 개념이 확실하게 잡혀있지 않아 확실하게 이해하고 문제를 풀이하는데 오랜 시간이 걸렸다.