Coding Test/Python
[백준/DP] 11057번: 오르막 수 (실버1, python)
lim.dev
2024. 2. 1. 14:27
https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
아이디어
DP문제였다.. 규칙을 못 찾아서 검색했다 ㅠㅠ..
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | total | |
| N = 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 10 |
| N = 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 55 |
| N = 3 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 | 220 |
행은 길이가 N일 때
열은 해당 숫자로 끝나는 경우의 수이다.
이 표에서 찾을 수 있는 규칙은 다음과 같다.
[i][j] = [i-1][j] + [i][j-1]
* 0일때 경우의 수는 계속 1개니까 (0, 00, 000, 0000...) 점화식을 사용해도 문제가 없다.
전체 코드
N = int(input())
dp = [1] * 10
for _ in range(1, N):
for j in range(1, 10):
dp[j] += dp[j-1]
print(sum(dp) % 10007)
찾은 점화식은 [i][j] = [i-1][j] + [i][j-1]인데 코드 상에서 dp[j] += dp[j-1]인 이유는 2차원 배열로 구하지 않고 i-1의 배열에서 바로 값을 구하기 때문이다. (i-1의 배열의 원래 값에 j-1을 더하기 때문에 [i-1][j] + [i][j-1]이 된다. )