[백준 BOJ] 11057 오르막 수(python)

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

11057번: 오르막 수

 

 

🔥 작성 코드

# 오르막 수

n = int(input())

dp = [1] * 10
while n > 1:
    for i in range(1,10)[::-1]:
        dp[i] = sum(dp[0:i+1])
    n -= 1

print(sum(dp)%10007)

 

 

⭕ 해설

 

1. 일단 n이 1인 경우를 먼저 생각했습니다.

가장 앞에 오는 수	개수
0	1
1	1
2	1
3	1
4	1
5	1
6	1
7	1
8	1
9	1
sum	10

 

2. 이 상태에서 n=2가 된다면 0 앞에는 0밖에 올 수 없습니다. 마찬가지로 모든 수에 대해 생각해본다면,

• 1의 앞에는 0, 1가 올 수 있습니다.
• 2의 앞에는 0, 1, 2가 올 수 있습니다.
•  ...
• 8의 앞에는 0, 1, 2, 3, 4, 5, 6, 7, 8가 올 수 있습니다.
• 마지막으로 9의 앞에는 0부터 9까지 모든 수가 올 수 있습니다.

그렇다면 앞이 9인 것은 계속 한 개일 것이고, 8은 그 전에 8과 9의 숫자만큼 더해지고, 7은 7, 8, 9의 숫자만큼 더해지고, 0은 모든 수의 숫자만큼 더해질 수 있습니다. 그래서 이 전개를 가지고 n=2, n=3에서 표를 다시 만들어보면

가장 앞에 오는 수	n =1일 때 개수	n = 2일 때 개수	n = 3일 때 개수
0	1	10	55
1	1	9	45
2	1	8	36
3	1	7	28
4	1	6	21
5	1	5	15
6	1	4	10
7	1	3	6
8	1	2	3
9	1	1	1
sum	10	55	220

3. 이 표를 토대로 n=1일 때의 dp리스트를 작성해두고, n이 1보다 클 때 동안 가장 앞에 있는 숫자를 기준으로 

• 모든 수의 개수를 더한 것을 0의 자리
• 0을 제외한 모든 수의 개수를 더한 것을 1의 자리
• 0과 1을 제외한 모든 수의 개수를 더한 것을 2의 자리
• ...
• 8과 9의 수를 더한 것을 8의 자리
• 9는 계속 1

위와 같이 dp를 갱신해줍니다.

 

 

🚨dp 리스트에 담긴 순서는 [9의 개수, 8의 개수, 7의 개수, 6의 개수, 5의 개수, 4의 개수, 3의 개수, 2의 개수, 1의 개수, 0의 개수]이므로 i의 범위를(1,10)[::-1] 로 잡았습니다.

 

공부를 하면서 제 생각을 정리하기 위해 작성하는 글이니 이것보다 쉽고 효율적인 코드가 얼마든지 있을 수 있습니다.