백준 11057. 오르막 수(python)
2023. 4. 23. 22:54ㆍ카테고리 없음
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
입력
- 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다.
문제 풀이
- N자리 수 중 오르막수의 개수를 구해야한다.
- N-1 자리 수의 각 끝자리 별 오르막 수의 개수를 알면 N 자리 수의 오르막 수의 개수를 알 수 있다.
N = int(input())
dp = [[0 for _ in range(10)] for _ in range(N+1)]
if N == 1:
print(10)- N이 1이라면 오르막 수는 10개 이므로 10을 출력한다.
else:
for i in range(10):
dp[1][i] = 1
for i in range(2, N+1):
for j in range(1, 11):
for k in range(j):
dp[i][j-1] += dp[i-1][k]%10007
sum = 0
for i in range(10):
sum += dp[N][i]%10007
print(sum%10007)- N이 2 이상이면 자리수(행), 끝 자리(열, 0~9)를 나타내는 2차원 리스트를 만든다.
- 1행은 모두 1로 초기화하고, 나머지는 0으로 초기화한다.
- i자리 수 중 3으로 끝나는 수는 i-1자리 수 중 끝자리가 0, 1, 2, 3인 수로 만들 수 있다.
- 위와 같은 방식으로 자리 수를 늘려간다.
- 10007으로 나눈 나머지를 구해야하므로 중간과정에서 계속 나머지를 구해 더해준다.
