백준 10844 - 쉬운 계단 수

문제 설명

 

 

dp임을 알고서도 푸는데 많이 헤멘 문제였다. 

 

dp[자릿수] [들어갈 수 있는 숫자] = 가능한 경우의 수 

로 잡고 bottom up의 방법으로 풀었다. 

 

 

*알고리즘

1. 처음자리의 숫자는 1~9까지만 들어갈 수 있으므로 1개의 가지수씩 들어갈 수 있다.

 

2. 해당 자리숫자에
   1)0인 경우 : 이전 숫자가 1인 경우
   2)9인 경우 : 이전 숫자가 8인 경우 
   3)1~8 : 나머지

 

이를 점화식으로 나타낼 시

 

 

1) j==0              dp[i][j]=dp[i-1][j+1]

2) j==9              dp[i][j]=dp[i-1][j-1];

3) 나머지           dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];

 

 

로 짤 수있다. 

3. 내가 원하는 자릿수의 0~9까지 가능한 가지의 수를 모두 더한다

 

 

***mod의 숫자가 int의 범위를 벗어나므로 dp array와 sum 역시 long long으로 해줘야하는 것을 명심하자.

 

 

//
//  main.cpp
//  Baekjoon
//
//  Created by 이준후
//  Copyright © 2020 이준후. All rights reserved.
//

#include <iostream>
#include <vector>
#define mod 1000000000
using namespace std;

int main()
{
    long long dp[101][10]={};//자릿수, 들어갈 수 있는 숫자
    long long sum=0;
    int N;// variable ~100
    
    cin>>N;
    
    for(int i=1;i<10; i++)
    {
        dp[1][i]=1;
    }
    
    for(int i=2; i<=N; i++)
    {
        for(int j=0; j<10; j++)
        {
            if(j==0)
            {
                dp[i][j]=dp[i-1][j+1];
            }
            else if(j==9)
            {
                dp[i][j]=dp[i-1][j-1];
            }
            else
            {
                dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1];
            }
            dp[i][j]%=mod;
        }
    }
    
    for(int i=0; i< 10; i++)
    {
        sum+=dp[N][i];
    }
    cout<<sum%mod<<'\n';
    
    return 0;
}