[백준 알고리즘] 10844번 쉬운 계단 수

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째줄에 N이 주어진다 N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다

정답은 1,000,000,000으로 나눈 나머지를 출력한다

풀이

f(n, i) = 길이가 n인 i로 시작하는 계단 수가 몇개인지

f(1, 1) =1 f(1, 2) =1 .... f(1, 9)=1 

f(2, 1) = f(1,2) -> 길이가 2인 1로 시작하는 계단수는 길이가 1일때 2로 시작하는 계단수에 1을 붙이는거

f(2, 2) = f(1,1)+f(1, 3) -> 길이가 2인 2로 시작하는 계단수는 길이가 1일때 1, 3으로 시작하는 계단수에 2붙이는것

f(2, 3) = f(1, 2)+f(1, 4)

...

f(n, 1) = f(n-1, 2)

f(n, 2) = f(n-1, 1)+f(n-1, 3)

f(n, i) = f(n-1, i-1)+f(n-1, i+1)

하게되면 10 와 같은 계단수를 계산 못한다....

10은 길이가 2이고 1로 시작하는 계단수에 생긴다 

101은 길이가 3이고 1로 시작하는 계단수

1010 길이가 4이고 1로 시작하는계단수

10101 길이가 5이고 1로 시작하는계단수 가 하나씩 생긴다 매자리마다 

f(n, 1) = f(n-1, i+1) +1 로!!!!!

라고 잘못생각했다ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

f(n,  0) 을 이용해야했다!

코드

dp[1][0] = 0;

for (i = 1; i <= 9; i++)

dp[1][i]=1;

for (i = 2; i <= n; i++)

{

for (j = 0; j <= 8; j++)

{

if (j == 0)

dp[i][j] = (dp[i - 1][j + 1]) % 1000000000;

else

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])%1000000000;

}

dp[i][j] = dp[i - 1][j - 1]%1000000000;

}

for (i = 0; i <= 9; i++)

result = (result+dp[n][i])%1000000000;

printf("%lld ", result%1000000000);

*f(n,0)을 이용하는거에서 이해를 못할뻔했는데 나는 맨앞에 새로운 자릿수를 붙이려했는데 0으로 시작하는 수는 없기때문에 맨 뒤에 붙인다고 생각을 해야하고 마지막 result에서 더할때도 0부터 9까지..였다