[백준] 1038 감소하는 수 - 골드 5

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

 

 

주어진 문제는 다음과 같다.

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소하는 수의 N 번째 수를 찾는 것이다.

 

주어진 예제를 통해 문제를 살펴보자

 

주어진 예제에서 18번째 감소하는 수는 42라고 한다.

 

이를 직접 세어보면

0번째 감소하는 수는 0

1번째 감소하는 수는 1

.

.

.

9번째 감소하는 수는 9

10번째 감소하는 수는 10 이 되며

11번째 감소하는 수는 20이 된다.

12는 21, 13은 30 이런식으로 18번째 수는 42가 되는 것이다.

 

이를 통해 확인할 수 있는 것은 감소하는 수를 만들어야 하며 만들수 있는 최대의 감소하는 수는 9,876,543,210 이 될 것이다.

이 이상의 수는 넣어봤자 감소하는 수의 조건에 만족하지 않기 때문이다.

이를 생각하면 코드를 작성해 보았다.

 

import sys
input = sys.stdin.readline

N = int(input())

if N <= 10:
    print(N)
else:
    N -= 11
    arr = [2, 0]
    while N != 0:
        for j in range(len(arr)-1, 0, -1):
            if arr[j] < arr[j-1]:
                if arr[j - 1] - 1 == arr[j]:
                    arr[j - 1] += 1
                    arr[j] = 0
                    N -= 1
                else:
                    arr[j] += 1
                    N -= 1
            
            if arr[0] == 9:
                if arr[j] + 1 == arr[j - 1]:
                    arr[0] = 1
                    for i in range(len(arr)-1):
                        arr[i+1] = 0
                    arr.append(0)
                    N -= 1

                    
    answer = ''
    for i in range(len(arr)):
        answer += str(arr[i])
    
    if int(answer) > 1000000:
        print(-1)
    else:
        print(answer)

 

처음 생각한 코드는 이렇게 작성했다.

N이 1자리 수라면 그대로 N을 출력하고 2자리 이상인 경우 N에서 11을 제외한 나머지 수만큼 while문을 반복할 생각이었다.

그러나 수의 자리수가 늘어나니 배열의 탐색 위치 설정이 복잡해졌고 조건에 맞지 않는 수가 출력되었다.

 

그래서 고민해본 결과 N 과 M 문제를 떠올리게 되었다.

N과 M 문제의 경우 백트래킹을 활용하여 중복되지 않는 모든 조합의 경우의 수를 만드는 문제이다.

이 문제 역시 모든 경우의 수를 만드는데 만들어진 경우의 수를 거꾸로 정렬하면 되는 문제인 것이다.

 

또한 파이썬에는 경우의 수를 만들어주는 유용한 라이브러리인 itertools 의 combinations 가 존재한다. 

 

따라서 해당 코드를 활용해 문제를 해결하였다.

 

import sys
input = sys.stdin.readline
from itertools import combinations

# 입력
N = int(input())
answer = []		# combinations으로 생성한 모든 경우의 수를 저장할 배열

# 0부터 9까지 최대 10자리의 자릿 수를 지정하기 위해 1부터 11의 범위 지정
for i in range(1, 11):

	# combinations 를 이용해 생성할 숫자의 범위 -> 0 ~ 10
    # 그 숫자의 범위 중 몇자리 까지 지정하는가 -> i
    for comb in combinations(range(0, 10), i):
        comb = list(comb)			
        comb.sort(reverse=True)
        answer.append(int("".join(map(str, comb))))

answer.sort()
try: 
    print(answer[N])
except:
    print(-1)

 

생성가능한 최대의 감소하는 수는 9876543210 으로 최대 10자리 입니다. 따라서 1부터 11의 범위를 지정해 

0 ~ 9 까지 최소 1자리부터 최대 10자리까지의 자릿수를 지정해 주기 위해 for i in range(1, 11) 을 사용해 주었습니다.

 

또한 combinations를 통해 생성할 경우의 수는 0~9 까지 모든 수를 이용하는 경우의 수 이고 그 숫자를 몇 자리까지 지정하느냐는 i로 통제해 줍니다.

 

따라서 i가 1인 경우 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 되고

i가 2인 경우 10, 20, 30, 40, 50, 60, 70, 80, 90, 21, 31, 41, 51 .... 이렇게 생성됩니다.

 

여기서 생성한 경우의 수 리스트 형식으로 형변환을 실시한뒤 뒤집어 줍니다. 그럼 생성 경우의 수가 뒤집혀 증가하는 경우의 수가 아닌 감소하는 경우의 수로 저장됩니다.

 

이렇게 뒤집어 저장한 리스트를 문자열로 형변환을 실시해 공백을 제거하여 answer 리스트에 넣어주는데 숫자 형식으로 넣어 출력조건을 맞춰 주었습니다.

 

마지막으로 입력된 N에 따라 결과를 출력하여야 하는데 해당 N 번째 숫자가 리스트에 없을 수 도 있습니다. 

그 조건을 제어해 주기 위해 try except 문을 사용해 결과를 출력해 주었습니다.

 

---

[결과]