백준 알고리즘 10844번 (DP)

 

백준 알고리즘 10844번

문제:  쉬운 계단 수

45656이란 수를 보자.

 

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

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

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

 

 

입력: 

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

 

출력:

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

 

풀이:   그림을 그려보면 쉽게 풀 수 있다.

1번째줄 :      1              2              3               4              5              6              7              8              9

2번째줄 :   0    2        1    3        4     4       3     5       4     6       4     7      6     8        7     9          8

3번째줄:    1

배열 dp[n][i]를 생성하였을 때 n을 자릿수 i를 일의 자리라 생각해야한다.

dp[1][i] = 1 로 초기화를 시켜주고 풀이를 진행하여야하는데 숫자 1은 경우의 수라 생각한다.

만약 n이 1로 주어진다면 dp[1][i] 에서 i번째가 1~9를 모두 더한 값이다. (합: 9)

그림을 3번째 줄 까지 그려보았을 때 0 과 9 에서는 하나밖에 생성되지않는 것을 볼 수 있다.

0 일 때는 오로지 + 1 만을 9일 때는 - 1만을 사용하여 아랫줄로 넘어가게 된다.

나머지 1~8 까지는 -1과 +1 두 개 모두 사용하여 아랫줄로 넘어가게된다.

그리하여  (i = 0)  dp[n][i] = dp[n-1][i+1]                                                                                                           (i = 9) dp[n][i] = dp[n-1][i-1]                                                                                                             (i=1~8) dp[n][i] = dp[n-1][i-1] + dp[n-1][i+1] 라는 점화식을 세울수있다.

 무슨 얘기냐 일의자리가 1~8까지의 수는 하면 첫 번째 줄에서 i(일의자리수에) -1, +1한 것이 두번째에 나온다는 것이다.

간단히 말하자면 일의 자리가 0,9 이면 다음 자릿수에는 경우의 수는 1개이고 1~8이면 다음 자릿수의 경우의 수가 2개라는 것이다. 

 

코드

 

입력이 되지 않아 에러가 발생한다.

 

느낀점 : 내가 이해를 못했음을 느낀다. 경우의 수를 구하는 DP였고 2차 배열을 통해 자릿수를 나타내는 것을 알게되었다. long type으로 2차배열을 선언하지 않을 시 오버플로우가 뜨는 것을 몰라 다른 블로그를 참고하고도 계속 틀린문제이다. 다른 블로그를 참고하였을 때는 초기화를 해주지 않은 배열은 0으로 들어가는 것을 이용해 i =9 일 때를 그냥 1~8 점화식에 넣어버렸다.