10844번 쉬운 계단 수 문제를 풀어보았다.

10844 쉬운 계단 수

 

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

10844번: 쉬운 계단 수

 

이번 문제는 쉬운 계단 수, 쉬운 계단 수란 자릿수마다 인접한 수들의 차이가 1만 차이가 난다.

즉, 4565456, 1234, 5654 같은 수는 쉬운 계단 수이다.

11이나 14, 1235 같은 수는 쉬운 계단 수가 아니다.

n자리수 숫자 중 쉬운 계단 수의 개수를 구해서 10억으로 나눠서 출력하는 문제이다.

n=1

1 2 3 4 5 6 ...

n=2

10 12 21 23 43 45 54 56 ...

대충 생각해보니, n자리수의 숫자는 n-1자리수에 인접한수 +-1만큼의 차가 난다.

즉, DP[i][j]=DP[i-1][j-1]+DP[i-1][j+1] 인 셈이다.

참고로 0의 경우는 인접한 수를 저렇게 계산하면 -1을 세기때문에 말이 안된다.

따라서 DP[i][0]=DP[i][1] 이 좋을 것이다.

9의 경우도 10을 세면 안되므로, 배열의 초기 크기를 11로 만들고 10번째 배열에 0을 넣어두면 될 것이다.

그렇게 해서 풀었는데, 처음에 풀때, 합 계산할 때 나누는 것을 생각하지 못한 탓에 내 시간이 20분 증발했다. (정말 쓸데없는데서 틀렸었다니 풀고나서 기분나빴다.)

 

#include <stdio.h>
int main()
{
    int n,i,j;
    long long int DP[101][11]={0},s=0;
    for(i=1; i<=9; i++) DP[0][i]=1;
    scanf("%d", &n);
    for(i=1; i<n; i++) {
        DP[i][0]=DP[i-1][1];
        for(j=1; j<=9; j++) DP[i][j]=(DP[i-1][j-1]+DP[i-1][j+1])%1000000000;
    }
    for(i=0; i<=9; i++) {s+=DP[n-1][i];s%=1000000000;}
    printf("%lld",s);
}