JArchive 프로그래밍 일기

문제

쉬운 계단 수 백준 10844번

리뷰

자리수 N이 1일 때, 2일 때의 계단 수들을 써봤다.

자리수 마다의 계단 수 합계에 규칙성이 있을 것 같았는데, 그렇지 않았다.

'0'은 반드시 앞에 1이 와야 하는 제한이 있고, ex) 10, 210

'9'는 반드시 앞에 8이 와야 하는 제한이 있었다. ex) 89, 789

0, 9와는 달리, '1'은 앞에 2가 와도 되고 0이 와도 된다. (이렇게 1부터 8까지는 제한이 없다.)

마지막 자리 숫자가 L인 계단수가 몇개인지를 기준으로 점화식이 필요하다.

[ 점화식 ]

자리수 N의 숫자들의 마지막 자리 숫자가 L이라고 한다.

arr [2] [3] 은 2자리 숫자 중에 마지막 자리 숫자가 3인 계단 수의 개수다. ex) 23, 43 이 된다.

arr [N] [L] = arr [N-1] [L-1] + arr [N-1] [L+1]

이 때, L의 범위는 1 <= L <= 8 이다.

왜냐하면 '0'은 앞에 1이 와야만 하고, '9'는 앞에 8이 와야만 하니까 따로 관리한다.

(계단 수는 0으로 시작하지 않음)

1자리 수과 2자리 수의 계단 수 개수

2자리 수 중에서(N = 2) , 마지막 자리 숫자가 2인 경우(L = 2)를 보면, 12와 32가 있다.

2 앞에는 1과 3이 올 수 있다.

즉, 1자리 숫자에서 마지막 자리 숫자가 1인 계단수의 개수, 마지막 자리 숫자가 3인 계단수의 개수 가 몇 개냐에 따라 결정된다.

식으로 정리하면 , arr [2] [2] = arr [1] [1] + arr [1] [3]

arr [N] [L] = arr [N-1] [L-1] + arr [N-1] [L+1]

그리고 유의할 점.

1000000000 으로 나눈 값을 출력해야 하니까, 배열에 저장할 때 부터 mod 연산을 해야 한다.

처음에는 sum을 int로 선언했었는데, 1000000000 때문에 long long을 바꾸니까 맞았다.

코드

#include <stdio.h>
#define MODNUM 1000000000 
using namespace std;

int arr[101][11];

int main(void){

    int n = 0, i = 0, j = 0;
    long long sum = 0;

    scanf("%d", &n);

    for(i=1; i<=9; i++){  // 0을 제외한 1자리 수들은 모두 계단 수가 1개.
        arr[1][i] = 1;
    }

    for(i = 2; i <= n; i++){ //  n : 몇 자리 수 인지  

        for(j=0; j <= 9; j++){ //  숫자의 마지막 자리 수  

            if(j == 0) 
                arr[i][0] = arr[i-1][1] % MODNUM;
            else if(j == 9) 
                arr[i][9] = arr[i-1][8] % MODNUM;
            else 
                arr[i][j] = ( arr[i-1][j-1] + arr[i-1][j+1] ) % MODNUM;
        }
    }

    for(i = 0; i <= 9; i++){  
        sum += arr[n][i];
    }

    printf("%lld", sum % MODNUM); // 마지막에 mod 연산 

    return 0;
}