백준 1038. 감소하는 수 (파이썬)

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

 

해설

이 문제는 제대로 안 읽으면 헷갈릴 수 있다. 난이도가 solved.ac 기준 골드 5인데, 문제 자체가 어렵게 쓰여서 골드 5인듯하다. 알고리즘 자체는 어렵지 않다.

N번째 감소하는 수란, 0부터 시작해서 감소하는 수 집합에서 N번째 수는 무엇인지 묻는 문제이다. 

여기서 감소하는 수란, 주어진 숫자의 맨 첫자리부터 끝자리까지 계속해서 감소하는 수를 의미한다.

따라서 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43, ..... 이렇게 계속 늘어나는 집합에서 N번째 감소하는 수는 무엇인지 묻는 것이다. 예제 입력으로 18이 주어졌는데 위 집합에서 18번째 수는 42 이기 때문에 42를 출력해야 정답이다.

 

코드를 보자.

N = int(input())

su_list = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]


def dp() -> int:
    if N < 10:
        return su_list[N]

    idx = 1
    while len(su_list) < N + 1:
        if len(su_list) <= idx:
            return -1
        for s in range(0, int(su_list[idx][-1])):
            desc = su_list[idx] + su_list[s]
            su_list.append(su_list[idx] + su_list[s])
            if len(su_list) == N + 1:
                return su_list[-1]
        idx += 1

    return su_list[-1]


print(dp())

이 문제는, DP 알고리즘을 이용해서 풀 수 있다. DP란 Dynamic Programming의 약자로 우리나라 말로 동적 프로그래밍이라고 한다. 

DP 알고리즘의 특징은 저장할 수 있는 것은 저장해두고 필요할 때 저장된 것을 갖다씀으로써 연산 수를 줄이는 것이 특징이다. 그래서, su_list라는 배열을 선언해서 0~9까지 미리 넣어뒀다. 그 후, su_list에다가 연산의 결과 (감소하는 수를 만드는 연산)을 계속해서 삽입해서 주어진 N번째 요소가 리스트에 채워졌을 때 N번째 요소를 return하도록 하였다.

 

감소하는 수를 만드는 연산은 코드에서 while문 내부 로직을 참고하면 되는데, 우선 while에 들어가는 조건은 su_list의 길이가 주어진 N보다 작아야한다. 길이가 N이 되는 순간 함수가 종료되면서 N번째 요소를 return해야하기 때문이다.

 

while문 내부로 들어가면, N번째 감소하는 수가 없을 때를 대비해서 -1을 출력하는 조건문을 넣어두고, 그 조건을 만족하지 않는다면

for문으로 들어가게된다. for문에서 감소하는 수를 만들어준다. 이 때, idx는 맨 앞에 붙는 수인데, for문을 0부터 su_list의 idx번째의 가장 마지막 자리수까지 돈다. idx는 1부터 시작하고 su_list의 1번째에는 1, 2번째에는 2가 들어가있으므로, su_list의 idx번째의 가장 마지막자리 수까지 돌도록 범위를 설정하였다. 끝에 -1번째 옵션을 붙인 이유는 0~9까지만 붙일 수 있도록 하기 위해서다. (그냥 idx까지만하면 10, 20과 같은 수도 붙으므로)

 

for문을 다 돌고나면 idx를 하나 증가시켜서 감소하는 수를 만들어나간다.

 

while의 조건이 False가 되면 (N번째 수가 만들어지면) 함수가 종료되면서 값을 출력하게된다.