[백준] 10844번 쉬운 계산 수 (C)

문제 주소

백준 10844번 쉬운 계산 수

 

10844번: 쉬운 계단 수

알고리즘

DP

 

힌트

dp배열에 i자리수중 j로 끝나는 수의 개수를 저장한다.

 

문제풀이

dp배열에 i자리 수중 j로 끝나는 수의 개수를 dp[i][j]에 저장한다. 0으로 끝나는 경우와 9로 끝나는 경우 그 이전의 수가 될 수 있는 수는 1과 8밖에 없기 때문에 따로 처리해준다.

#include<iostream>
using namespace std;
int dp[101][10];
int main(){
    int n;
    cin>>n;
    //초기항 설정 
    for(int i=1;i<=9;i++){
        dp[1][i]=1;
    }

    //찾기 
    for(int i=2;i<=n;i++){
        dp[i][0]=dp[i-1][1]%1000000000;
        dp[i][9]=dp[i-1][8]%1000000000;
        for(int j=1;j<=8;j++){
            dp[i][j]=(dp[i-1][j-1]%1000000000+dp[i-1][j+1]%1000000000)%1000000000;    
        }
    }
    int ans=0;
    for(int i=0;i<=9;i++){
        ans+=dp[n][i];
        ans%=1000000000;

    }
    cout<<ans%1000000000;
}

백준 10844번 쉬운 계산 수 (C)