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

계단 오르기 2

 

문제

이 문제는 한번에 1, 2, 3계단씩 오를 수 있는 n개의 계단이 존재할 때 계단을 오를 수 있는 경우의 수를 1000으로 나눈 나머지를 출력하는 문제이다.

 

풀이

DP 문제로 코딩을 하기전에 점화식을 생각해봐야한다.

 

계단을 오르는 경우의 수는 1계단, 2계단, 3계단씩 오르는 경우가 있다.

 

n이 음수인 경우는 0가지

0 번째 계단을 올라가는 경우의 수는 1가지 (기저 사례)

1 ~ n 번째 계단을 올라가는 경우의 수는 n - 1 (1계단), n - 2 (2계단) , n - 3 (3계단)

 

※ 기저 사례 : 재귀 함수에서 더이상 쪼개질 수 없는 작업 (Base Case)

#include <iostream>
#include <vector>
// https://codeup.kr/problem.php?id=3704&rid=0
using namespace std;

const int MOD = 1000;

int countWays(int n, vector<int>& memo) {
    // 0 계단에 도달한 경우 1을 반환
    if (n == 0) return 1;
    // 음수인 경우 경우의 수가 없으므로 0을 반환
    if (n < 0) return 0;

    // 이미 계산한 값이 있는 경우 해당 값을 반환
    if (memo[n] != -1) return memo[n];

    // 1계단, 2계단, 3계단을 오르는 경우의 수를 재귀적으로 더함
    memo[n] = (countWays(n - 1, memo) + countWays(n - 2, memo) + countWays(n - 3, memo)) % MOD;

    return memo[n];
}

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

    // memo 배열 초기화
    vector<int> memo(n + 1, -1);

    cout << countWays(n, memo) << endl;

    return 0;
}

 

 

반복문으로 풀이한 방법도 올리겠다.

 

반복문은 0 ~ 2 번째 계단을 올라가는 경우의 수를 저장하고,

3 ~ n 번째 계단을 올라가는 경우의 수를 위의 점화식을 이용하여 풀이했다. 

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000; // 결과를 1000으로 나눈 나머지를 저장하기 위한 상수

int countWays(int n) {
    // dp[i]는 i개의 계단을 오를 때 가능한 경우의 수를 저장하는 배열
    vector<int> dp(n + 1, 0);
    
    // 초기값 설정
    dp[0] = 1; // 0계단을 오르는 경우는 한 가지 방법이 있다.
    dp[1] = 1; // 1계단을 오르는 경우도 한 가지 방법이 있다.
    dp[2] = 2; // 2계단을 오르는 경우는 두 가지 방법이 있다. (1계단씩 오르거나, 2계단을 한 번에 오르거나)

    // 점화식을 이용하여 dp 배열 완성
    for (int i = 3; i <= n; ++i) {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % MOD;
    }

    return dp[n];
}

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

    cout << countWays(n) << endl;

    return 0;
}

 

 

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