백준 10844: 쉬운 계단 수 (Python)

문제

45656이란 수를 보자.

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

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

해설

 인접한 모든 자리의 차이가 '1'인 수를 계단 수라고 할 때, 길이 N ( 1 <= N <= 100 ) 의 계단수가 몇 개 있는지 구하는 문제다. N이 최대 100까지 입력될 수 있는데, 이때 수가 상당히 커지기 때문에 단순히 브루트포싱 or 백트래킹으로 풀게 되면 시간초과를 받는다. 그러므로 우리는 다이나믹 프로그래밍으로 문제에 접근해야 한다.

 

 DP 문제의 핵심은 복잡한 문제를 간단한 문제로 나누어 문제를 풀어가는 것이다. 제일 쉬운 것부터 생각해보자.

N이 1일 때, 계단 수는 몇개일까? 제일 앞의 자릿수가 i인 경우에 대해 모든 계단수를 구해보자. 

 

i	계단수	DP[N][i]
0	-	0
1	1	1
2	2	1
3	3	1
4	4	1
5	5	1
6	6	1
7	7	1
8	8	1
9	9	1

 

 DP[N][i]는 '길이가 N이고 앞자리가 i인 계단 수의 개수'를 저장하는 리스트다. 

그럼 이제 N이 2인 경우를 생각해보자.

 

i	계단수	DP[N][i]
0	-	1
	'0' '1'
1	'1' '0'	2
	'1' '1'
2	'2' '1'	2
	'2' '3'
3	'3' '2'	2
	'3' '4'
4	'4' '3'	2
	'4' '5'
i	'i' + 'DP[N][i-1]'
	'i' + 'DP[N][i+1]

 

 DP[2][i]는 '길이가 2이고 앞자리가 i인 계단 수의 개수'를 저장하게 될 것이다.

그러니 이제 우리는 '십의 자리 수'가 i 인 계단 수의 개수를 구하게 될 텐데, 이때 미리 구해둔 '일의 자리 수가 i인 계단 수의 개수' 를 조합해 답을 구할 수 있다.

 

예를 들어보자. 십의 자리 수가 2인 계단 수를 구하려면 어떻게 해야 할까?

십의 자리 수는 고정이니, 바로 뒤에 오는 일의 자리수가 1 또는 3이어야 한다.

일의 자리수가 1, 3인 계단 수의 개수는 DP[1][1], DP[1][3] 에 담겨있다. 그러므로 우리는

DP[2][2] = DP[1][1] + DP[1][3] 과 같은 방법으로 십의 자리 수가 2인 계단 수를 구할 수 있는 것이다.

 

N이 3이 되어 백의 자리 수까지 본다고 해도 마찬가지다.

다시한번, N이 3이고 백의 자리 수가 2인 계단 수는 어떻게 구할까?

백의 자리 수는 고정이니, 바로 뒤에 오는 십의 자리 수는 1 또는 3이어야 한다.

십의 자리수가 1, 3인 계단 수의 개수는 DP[2][1], DP[2][3] 에 저장되어 있다.

DP[3][2] = DP[2][1] + DP[2][3] 을 구하면 백의 자리 수까지 계산이 가능하다.

 

모든 i에 대해 위와 같은 식을 세워주면 답을 구할 수 있다.

'90', '01' 과 같은 수는 계단수가 아니라는 점이다. 자릿수의 차이가 1이 아니기 때문이다.

이런 점을 고려하여 코드를 작성해야 한다.

 

코드

N = int(input())
DP = [[0] * 10 for _ in range(100)]
DP[0] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(1, N):
    DP[i][0] = DP[i-1][1]
    DP[i][1] = DP[i-1][0] + DP[i-1][2]
    DP[i][2] = DP[i-1][1] + DP[i-1][3]
    DP[i][3] = DP[i-1][2] + DP[i-1][4]
    DP[i][4] = DP[i-1][3] + DP[i-1][5]
    DP[i][5] = DP[i-1][4] + DP[i-1][6]
    DP[i][6] = DP[i-1][5] + DP[i-1][7]
    DP[i][7] = DP[i-1][6] + DP[i-1][8]
    DP[i][8] = DP[i-1][7] + DP[i-1][9]
    DP[i][9] = DP[i-1][8] 
    

print(sum(DP[N-1]) % 1000000000)

 

#백준 #0000번 #문제이름 #파이썬