[백준] 10844 쉬운 계단 수

이름은 쉬운데 문제는 전혀 쉽지가 않다..

 

계단 형식으로 된 숫자들을 찾는 건데 DP 문제라 규칙을 찾는 것이 가장 중요하다!!

 

하지만 규칙을 찾으려고 자리 수별로 숫자도 세보고,, 자리 수의 첫 번째 자리, 마지막 자리만 떼서 규칙을 찾아봤지만 이런거로는 규칙을 찾을 수 없었다.. ㅠㅠ

도움을 받은 블로그..! 

https://yabmoons.tistory.com/22

[ 백준 10844 ] 쉬운 계단 수 (C++)

 

해당 블로그 해설을 보고 이해 한 후에 문제를 풀었다.

 

이런 문제를 보고 끝자리가 어떤 수가 오느냐에 따라서 규칙이 발생한다는 것을 어떻게 아는거지;

dp[i][j] 이차원 배열로 선언한다.

i는 입력받은 자리 수(1... 최대 100까지)가 들어가고, j는 끝나는 숫자 0...9가 들어가게 된다.

 

규칙을 보는 가장 중요한 방법!

 

손으로 직접 써보면 눈으로 쉽게 볼 수 있다.

하나하나 직접 숫자를 계산해가며 작성해 보았다.

위 표에서 추리할 수 있는 점화식은

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이다.

물론 j가 0, 9인 경우에는 특수적인 조건이 따른다.

 

j == 0인 경우

dp[i][0] = dp[i-1][j+1] 이고

 

j == 9인 경우

dp[i][9] == dp[i-1][j-1] 이다.

 

이런문제를 많이 풀어봐야 겠다는 생각이 들었다..ㅜ

 

□ 전체 코드

#include <bits/stdc++.h>
#define MOD 1'000'000'000
using namespace std;

void easy10844(){
    int n;
    scanf("%d",&n);

    long long dp[n+1][10];
    
    dp[1][0] = 0;
    for(int i=1;i<=9;i++){
        dp[1][i] = 1;
    }
    
    for(int i=2;i<=n;i++){
        for(int j=0;j<=9;j++){
            if(j==0){
                dp[i][j] = (dp[i-1][j+1] % MOD);
            }
            else if(j==9){
                dp[i][j] = (dp[i-1][j-1] % MOD);
            }
            else{
                dp[i][j] = (dp[i-1][j-1] % MOD) + (dp[i-1][j+1] % MOD);
            }
        }
    }
    
    long long result = 0;
    for(int j=0;j<=9;j++){
        result += (dp[n][j]  % MOD);
    }
    
    printf("%lld\n", (result  % MOD));
}