백준 10844 쉬운계단 수

문제

문제링크 : https://www.acmicpc.net/problem/10844

풀이전략

1. 0과 9에서 예외조건이 발생하므로 이를 잘 생각해야한다.
2. 0과 9를 제외한 나머지 조건은 다음식을 만족한다.
   dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1]
   즉 4번째 숫자 5를 예를 들면, 이 항의 값은 3번째 숫자 4의 개수와 3번째 숫자 6의 개수의 합으로 계산할 수 있는 것이다.

코드

#include<bits/stdc++.h>

using namespace std;

#define mine

const int MOD = 1000000000;
int N;
int dp[11][101];

int stairNum(){
    for(int i=1; i<=9; i++){
        dp[i][1] = 1;
    }
    
    for(int i=2; i<=N; i++){
        
        dp[10][i] = 0 ;

        for(int j=0; j<=9; j++){
            if(j == 0) dp[j][i] =  dp[j+1][i-1];
            else dp[j][i] = (dp[j-1][i-1] + dp[j+1][i-1])%MOD;
        }
    }
    
    int ret = 0;
    for(int i=0; i<=9; i++){
        //// 여기도 함부러 += 하면서 %쓰면 틀린다.
        ret = (ret +dp[i][N]) %MOD;
    
    }
    
    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);
    
    cin >> N;
    int res = 0;
    
    memset(dp, 0, sizeof(dp));
    

    cout<<stairNum()<<endl;

    return 0;
}

소감

이 문제는 해결하지 못하여 다른 사람의 블로그를 보았다. 여기서 0일때와 9일때의 특수조건을 주어서 문제를 쉽게 해결한 것을 보며 자유롭게 dp를 풀수 있도록 나아가야겠다.