[백준]동적 계획법1/쉬운 계단 수/10844 풀이 JAVA

문제

45656이란 수를 보자.

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

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

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

 

입력

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

 

출력

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

 

 

풀이(JAVA)

dp[N][index] = m이라고 할 때, 이는 N번째 자리가 index일 때 계단의 수가 m개임을 뜻한다.

예를 들면 dp[3][5] = 4;는

3의 자리가(100의 자리) 5일 때 계단의 수는 543, 545, 567, 565로 4개라는 뜻이다.

(※2의 자리는 10의 자리, 4의 자리는 1000의 자리이다.)

 

아래 표를 보며 문제를 이해해보자.

 

N = 1일 때 계단의 수 = 9

dp[1][0~9] = 9; 

N/index	0	1	2	3	...	6	7	8	9
1	1	1	1	1	1	1	1	1	1

1계단

0

1

2

3

...

6

7

8

9

 

N = 2일 때 계단의 수 = 17

dp[2][0~9] = 17;

N/index	0	1	2	3	...	6	7	8	9
1	1	1	1	1	1	1	1	1	1
1 계단	0	1	2	3	...	6	7	8	9
2	1	2	2	2	2	2	2	2	1
2 계단	01	10, 12	21, 23	32, 34	...	65, 67	76, 78	87, 89	98

(dp[2][0] = 1의 01에서 파란 부분은 인덱스, 빨간 부분은 dp[1][1]의 계단, 마찬가지로

dp[2][1] = 2의 10, 12에서 파란 부분은 인덱스, 빨간 부분은 dp[1][0]과 dp[1][2]의 계단...)

 

N = 3일 때 계단의 수 = 32

dp[3][0~9] = 32;

(앞에 생략된 부분은 위와 같음)

N/index	0	1	2	3	...	6	7	8	9
2계단	01	10, 12	21, 23	32, 34	...	65, 67	76, 78	87, 89	98
3	2	3	4	4	...	4	4	3	2
3계단	010, 012	101, 121, 123	210, 212, 232, 234	321, 323, 343, 345	...	654, 656. 676. 678	765, 767, 787, 789	876, 878, 898	987. 989

(dp[3][0] = 2의 010, 012에서 초록 부분은 인덱스, 파란 부분은 dp[2][1]의 계단, 마찬가지로

dp[3][1] = 3의 101, 121, 123에서 초록 부분은 인덱스, 파란 부분은 dp[2][0]과 dp[2][2]의 계단,

dp[3][2] = 4의 210, 212, 232, 234에서 초록 부분은 인덱스, 파란 부분은 dp[2][1]과 dp[1][3]의 계단...)

 

표를 잘 이해했다면 점화식도 쉽게 알 수 있다.

dp[N][index] = dp[N - 1][index - 1] + dp[N - 1][index + 1]이다.

 

이때 주의해야 할 점은,

index가 0일 때는 index - 1에서 -1,  index가 9일 때 index + 1에서 10이라 인덱스 에러가 난다.

이는 0다음에 -1이 아닌 1만 올 수 있음과 9 다음에 10이 아닌 8만 올수 있음을 나타낸다.

이 부분의 예외를 잘 표현해주면 아래 코드와 같이 나타낼 수 있다.

 

 

 

(dp배열을 dp[N + 1][10]이 아니라 dp[N][index]로 만든 풀이)

---

한 번 이해하고 나니 코드가 쉽게 짜지는.... 거 같기도!?