[백준] 동적 계획법 - 10844번: 쉬운 계단 수 (Java)

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

10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

문제이름은 쉬운 계단 수 이지만 쉽지 않은 문제였다.

하지만 표를 만들어서 조금 고민해보니까 금방 해결할 수 있었다.

길이가 1일 때에는 1, 2, 3, ··· , 8, 9로 총 10개, 길이가 2 일 때에는 10, 12, 21, 23 , ···, 89로 총 17개 이다.

길이가 점점 늘어나면 개수가 정말 많이 늘어나서 노가다로 쓰기에는 쉽지않다.

규칙을 찾아보자.

우선 표를 그려서 행은 계단수의 끝자리를 나타내고 열은 계단수의 길이를 나타낸다.

길이가 1 일 때에는 끝자리가 0일 때를 제외하고 1이고 2 일때에는 끝자리가 0일 때만 1이고 나머지는 2 이다. 나는 규칙을 더 찾고자 4까지 노가다를 했다. 그러고 나서 표를 보니 규칙이 보인다.

계단수는 앞 뒤로 1 씩 차이나는 수이다. 길이가 3 일때 끝자리가 3인 수를 예로 들자. 123, 323, 343, 543이다. 얘네들을 잘 보면 맨 오른쪽에서 두번째 수를 보면 3과 1 차이나는 수(12, 32, 34, 54) + 3이다.

결국 길이가 하나 작은 계단수에서 끝자리에서 하나씩 차이나는 아이들을 찾으면 해결이다.

이것을 점화식으로 나타내면 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] 이다.

j == 0 일때와 j == 9 일때 처리 해주고, 10억을 신경써서 나누어주면 문제는 해결된다.

길이\끝자리	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	2	2	2	2	2	2	2	2	1
3	2	3	4	4	4	4	4	4	3	2
4	3	6	7	8	8	8	8	7	6	3