[백준(BOJ)] 10844번: 쉬운 계단 수 (Dynamic Programming, C++)

📝 문제풀이 과정

---

• DP[n]: n자리 수에서 만들 수 있는 계단 수의 개수
• DP[0] = 9 (1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9)
• DP[n][m]에서 n이 앞자리, m이 뒷자리

• 초기 값: N이 1일 때, 0~9가 올 수 있으므로 DP[1][i]에 대해 count를 1로 할당해준다.
• 2 ~ N까지(N번째 자리) 0 ~ 9의 수가 올 수 있는데, 각 경우에 대해 점화식을 만들어준다.
  • DP[i][0] = DP[N-1][1] : 둘째 자리가 0인 경우, 앞에는 1만 올 수 있다. (이전이 1이어야 함을 나타냄)
  • DP[i][9] = DP[N-1][8] : 9인 경우, 주변에 8만 올 수 있다. 
  • DP[i][j] = DP[N-1][i-1] + DP[N-1][i+1] : 그 이외의 경우, 즉 1 ~ 8의 경우, 해당 숫자보다 1 작거나, 1 큰 수가 올 수 있다.

 

💻 C++ 제출코드

---

#include <stdio.h>

int main(){
    int N;
    scanf("%d", &N);

    int DP[N+1][10] = {};

    for(int i=0; i<10; i++){
        DP[1][i] = 1; // 1_ 일 때 0 ~ 9 저장
    }
    for(int i=2; i <= N; i++){
        for(int j=0; j<10; j++){ // 0 ~ 9
            if(j == 0) DP[i][0] = DP[i-1][1]; // 뒷자리가 0일 때 앞은 1
            else if(j == 9) DP[i][9] = DP[i-1][8]; // 9가 올 때 이전은 8 또는 이후는 8
            else DP[i][j] = (DP[i-1][j-1] + DP[i-1][j+1]) % 1000000000; // 1 ~ 8 의 경우, +1 수 또는 -1 수
        }
    }
    int sum=0;
    for(int i=1; i<10; i++){ // N자리일 때의 모든 경우의 수를 더해줌
        sum = (sum + DP[N][i]) % 1000000000;
    }
    printf("%d", sum % 1000000000);
    
}

 

 

👏 결과

---