[백준] 1038번 : 감소하는 수

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

1038번: 감소하는 수

해당 문제는 다이나믹 프로그래밍으로 문제를 해결 하였습니다. N 자리수의 값을 구할때 N-1 자리수에서 가져와 이어 붙힙니다.

예를들어서30,31,32 을 (두번째자리) 구한다고하면 3보다 작은 N-1 자리수에 3을 이어붙힌 값인 310, 320, 321 입니다.

[10]은 1로 시작하는 2번째 자리수, [20,21] 2로 시작하는 2번째 자리수 입니다.

dp[3] = prev_dp[2] + prev_dp[1] 이라는 점화식이 만들어집니다.

dp[n] = prev_dp[n-1] + ... + prev_dp[0] 이라는 점화식을 세울 수 있습니다.

 

N = int(input())

dp = [[] for _ in range(10)]
for i in range(10):
    dp[i].append(i)

result = [0,1,2,3,4,5,6,7,8,9]
for i in range(1, 10): # 자리수 반복 ( 두번째 자리수 부터 시작)
    temp_list = [[] for _ in range(10)]
    for j in range(1, 10):
        for k in range(j):
            for num in dp[k]:
                temp_list[j].append(int(str(j) + str(num)))
                result.append(int(str(j) + str(num)))
    
    dp = temp_list

if len(result) > N:
    print(result[N])
else:
    print(-1)