[백준] 10844번: 쉬운 계단 수 풀이 및 해설(C++)

문제 이미지

 

풀이

수열에서 n번째 중 몇 번째에 오는지 표시하는 열과, 1~9까지의 수를 나타내는 열로 2차원 배열 arr을 만든다.

그리고 배열에는 그 번째가 그 숫자로 끝날 때의 값을 넣는다. 가령 arr [2][3] 은 2번째 자리가 3으로 끝날 때의 계단 수이다.

계단 수의 규칙에 따라,

0으로 끝났다면 앞 수는 1이어야만 계단수이다.

1로 끝났다면 앞 수는 0이나 2여야만 계단수이다.

2로 끝났다면 이전수는 1이나 3이어야만 계단수이다.

3으로 끝났다면 이전수는 2나 4여야만 계단수이다.

 

.

.

.

8로 끝났다면 이전수는 7이나 9이어야만 계단수이다.

9로 끝났다면 이전수는 8이어야만 계단수이다.

 

 

즉, arr [m][n]=arr [m-1][n+1]+arr [m-1][n-1]이다. (단, n이 0이면 arr [m][n]=arr [m-1][n+1], n이 9면 arr [m][n]=arr [m-1][n-1]이다.)

 

단 0으로 시작한 경우는 계단수가 될 수 없다고 했다. 따라서 처음 케이스에 arr [1][0]만 0으로 두고 다른 arr[1] 들은 1로 설정한다.

 

이제 이 식을 그냥 더하지 말고, 출력조건에 맞게 1,000,000,000로 나눈 나머지로 더한 후, 마지막 열을 다 더해 출력한다.

 

해답 코드

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;


int main(){
    fastio;
    long long n,sum=0;
    long long arr[101][10];
    cin>>n;
    arr[1][0]=0;
    for(int i=1; i<10; i++){
        arr[1][i]=1;
    }
    if(n==1){
        cout<<'9';
        return 0;
    }
    for(int i=2; i<n+1; i++){
        arr[i][0]=arr[i-1][1]%1000000000;
        for(int j=1; j<9; j++){
            arr[i][j]=(arr[i-1][j-1]+arr[i-1][j+1])%1000000000;
        }
        arr[i][9]=arr[i-1][8];
    }
    for(int j=0; j<10; j++){
        sum=(sum+arr[n][j])%1000000000;
    }
    cout<<sum;
    
    return 0;


}