문제 바로가기
문제:
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.
입력:
첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.
출력:
첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.
풀이:
import sys
N = int(input())
dp = [[0] * 10 for _ in range(N)] # dp[길이][시작수]
for i in range(10):
dp[0][i] = 1
for i in range(1,N):
for j in range(10):
dp[i][j] = sum(dp[i-1][j::])
print(sum(dp[N-1])%10007)
#dp[2][1] 길이가 2이고 시작이 1인숫자, dp[1] 시작이 1,0 더해주면됨 dp[2][0] 이면 그대로
오랜만에 쉽게 풀었다.
dp는 2차원 배열로 선언을 해 주었다.
dp[문자길이][시작숫자] 값으로 선언을 해주었다.
dp[1][i] = 전부다 1이다
길이가 1일때 나올 수 있는 숫자는 각각 0,1,2,3,4,5,6,7,8,9 이기 때문에 1개씩이다.
dp[2][i] 는 길이가 2일때 나올수 있는 숫자인데 예를들면
dp[2][0] 은 00,01,02,03,04,05,06,07,08,09 >> 10개
dp[2][1] 은 11,21,31,41,51,61,71,81,91 >> 9개
...하면된다.
그것을 점화식으로 세우면
for i in range(1,N):
for j in range(10):
dp[i][j] = sum(dp[i-1][j::])
만약에 dp[3][4] 을 구하게 되면 길이가 3 이면서 시작이 4 인값인데 그 값은
dp[2][4::] 를 구하면 된다. 그 이유는 큰 숫자들은 다 들어갈 수 있기 때문이다.
ex) 4xx 를 구하는 것은 길이가 2 인 1x,2x,3x 는 필요가없다 41x, 42x, 43x 는 오름수가 아니기 때문이다
반대로 5x,6x... 은 들어가도 가능하다, 그러므로 가능한 모든 수를 더해줘서 dp[i][j]에 최신화 시켜주면 된다.
댓글