[Python] 백준 10844번 - 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 다이나믹 프로그래밍

 

문제

45656이란 수를 보자.

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

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

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

출력

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

 

---

 

DP문제라는 걸 알아차리는데도 오래 걸렸으나 규칙성을 찾고 이해하는 데는 더 오랜 시간이 걸렸다.

 

우선 정답코드

 

import sys
input = sys.stdin.readline

n = int(input())

dp = [ [0] * 10 for _ in range(n+1)]

for i in range(1, 10):
    dp[1][i] = 1

for i in range(2, n+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = dp[i-1][1]
        elif j == 9:
            dp[i][j] = dp[i-1][8]
        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
            
            

print((sum(dp[n])) % 1000000000)

 

일단 나는 규칙성을 찾기위해 1자리 숫자부터 5자리 숫자까지 모든 경우의 수를 찾았다.

 

1 자리
1
2
3
4
5
6
7
8
9

2자리
10 12
21 23
32 34
43 45
54 56
65 67
76 78
87 89
98

3자리
101 121 123
210 212 232 234
321 323 343 345
432 434 454 456
543 545 565 567
654 656 676 678
765 767 787 789
876 878 898
987 989 

4자리
1010, 1012, 1210, 1212, 1232, 1234, 
2101, 2121, 2123, 2321, 2323, 2343, 2345, 
3210, 3212, 3232, 3234, 3432, 3434, 3454, 3456, 
4321, 4323, 4343, 4345, 4543, 4545, 4565, 4567, 
5432, 5434, 5454, 5456, 5654, 5656, 5676, 5678, 
6543, 6545, 6565, 6567, 6765, 6767, 6787, 6789, 
7654, 7656, 7676, 7678, 7876, 7878, 7898, 
8765, 8767, 8787, 8789, 8987, 8989, 
9876, 9878, 9898

5자리
10101, 10121, 10123, 12101, 12121, 12123, 12321, 12323, 12343, 12345, 
21010, 21012, 21210, 21212, 21232, 21234, 23210, 23212, 23232, 23234, 23432, 23434, 23454, 23456, 
32101, 32121, 32123, 32321, 32323, 32343, 32345, 34321, 34323, 34343, 34345, 34543, 34545, 34565, 34567, 
43210, 43212, 43232, 43234, 43432, 43434, 43454, 43456, 45432, 45434, 45454, 45456, 45654, 45656, 45676, 45678, 
54321, 54323, 54343, 54345, 54543, 54545, 54565, 54567, 56543, 56545, 56565, 56567, 56765, 56767, 56787, 56789, 
65432, 65434, 65454, 65456, 65654, 65656, 65676, 65678, 67654, 67656, 67676, 67678, 67876, 67878, 67898, 
76543, 76545, 76565, 76567, 76765, 76767, 76787, 76789, 78765, 78767, 78787, 78789, 78987, 78989, 
87654, 87656, 87676, 87678, 87876, 87878, 87898, 89876, 89878, 89898, 
98765, 98767, 98787, 98789, 98987, 98989

1자리는 9개

2자리는 17개

3자리는 32개

4자리는 61개

5자리는 116개로

 

숫자를 나열해서 보면 어딘가.. 규칙성이 있어 보였으나 딱히 없었다.

 

이후 각 자리 숫자별로 규칙성을 찾기위해 2차원 배열을 직접 그렸었다.

 

	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
2	1	2	2	2	2	2	2	2	1
3	3	3	4	4	4	4	4	3	2
4	4	7	7	8	8	8	7	6	3
5	10	11	15	15	16	15	14	10	6

 

가로 1~9는 시작하는 숫자의 개수

세로 1~5는 자릿수이다

 

보다보니 규칙성이 보이지 않는가?

 

2~8의 dp[i][j]값은 dp[i-1][j-1] + dp[i-1][j+1]

9의 값은 dp[i][j] = dp[i-1][8] 로 정의할 수 있었다.

 

근데 1은..?

 

하지만 역으로 가로를 끝나는 숫자로 생각하면 위의 테이블을 다시 계산할 수 있었다.

 

	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2
4	3	4	7	7	8	8	8	7	6	3
5	4	10	11	15	15	16	15	14	10	6

 

끝나는 숫자가 0인 개수

dp[i][0] = dp[i-1][1]

 

끝나는 숫자가 1~8인 개수

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

 

끝나는 숫자가 9인 개수

dp[i][9] = dp[i-1][8]

 

이런 결과가 가능한 이유는

 

출처: https://velog.io/@sun02/Swift-10844-%EB%B0%B1%EC%A4%80-%EC%89%AC%EC%9A%B4-%EA%B3%84%EB%8B%A8-%EC%88%98

위와 같은 로직으로 DP를 사용할 수 있기 때문이다.

 

이번에도 여러모로 생각할게 많은 문제였다.