[백준] 10844번: 쉬운 계단 수

https://www.acmicpc.net/problem/10818

문제

알고리즘 접근 방법

DP와 2차원 배열을 활용한다.

우리가 알아야 할 정보는 숫자 길이(N)과 끝자리 숫자 이다.
이를 2차원 배열에 저장해놓는다.

끝자리 숫자가 1이라면??
길이를 1만큼 늘렸을 때 생성될 수 있는 계단 숫자의 끝자리 숫자는는 2와 0이다.

이런식으로 1부터 8까지는 2개의 숫자를 추가로 생성한다.
그러나 0과 9는 특수한 경우이다. 각각 1과 8로부터만 생성될 수 있다.

이를 식으로 정리해보면

• i=1~8 : d[N][i] = d[N-1][i-1]+d[N-1][i+1]
• i = 0 : d[N][i] = d[N-1][i+1]
• i = 9 : d[N][i] = d[N-1][i-1]

풀이

#include <iostream>
#define mod 1000000000

using namespace std;

int main(){

    int N;

    cin >> N;
    int dp[N+1][10] = {0, }; // 길이수, 끝자리 숫자

    // 1만큼 길이일때 9개  
    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++){  // j는 끝 자리 숫자
            if (j == 0){ // j = 0 이면 1->0 
                dp[i][j] = dp[i-1][j+1];
            }
            else if(j == 9){ // j = 9 면 8->9
                dp[i][j] = dp[i-1][j-1];
            }
            else{ // j = 1 ~ 8 이면 +-1 더하기 (ex. j=1 : 2->1, 0->1)
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1];
            }

            dp[i][j] %= mod;
        } 
        
    }

    int sum = 0;
    for(int i=0; i<=9; i++)
        sum = (sum + dp[N][i]) % mod;

    cout << sum << endl;

    return 0;
}

정리

2차원 배열을 이용할 생각을 못했다. 까비

💡 참고 포스팅

ssinee님 블로그
guiyum님 블로그