[백준] 1038 파이썬 - 감소하는 수

문제

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

 

풀이

진짜 너무 오래걸려서 풀었다.

 

첫번째 풀이

감소하는 수의 입력 조건이 1,000,000 이하인줄 알고 for문을 돌며 감소하는 수인지 검사했다.

문제를 푼 후 제출했을 때 31퍼센트에서 계속 '틀렸습니다'가 떠서 머리를 쥐어뜯었다.

알고 보니, 감소하는 수 중 가장 큰 수인 9876543210까지 구해야 하는 거였다.

입력 조건은 N번째 감소하는 수를 구할 때의 N의 조건이었다. (문제 좀 잘 읽자.. )

 

두번째 풀이

1부터 9876543210 사이 수를 for문으로 돌리고, 시간복잡도를 줄일 for문을 탈출하는 조건을 추가해야된다고 생각했다.

사실 조건부터 시간복잡도가 말이 안된다. 이건 아닌 것 같았다.

dp문제인가 싶었지만 부합하는 조건을 찾을 수가 없었다....

 

세번째 풀이

알고보니 조합을 사용하는 문제였다.

1부터 9876543210 사이 숫자를 생각해보았을 때,

감소하는 수의 최소 자릿수는 1, 최대 자릿수는 10임을 알 수 있다.

 

따라서 0~9까지의 숫자들 중 자릿수 만큼의 조합을 구해 

내림차순으로 정렬해주면 감소하는 수를 구할 수 있다.

조합은 중복을 허용하지 않으므로 매우 간단하게 감소하는 수의 배열을 구할 수 있는 것이다.

 

 

코드

import sys
from itertools import combinations

input = sys.stdin.readline
n = int(input())
answer = []

# i는 자릿수 (1~10)
for i in range(1,11):
    # j는 0~9 사이의 수 중 i자릿수 만큼의 조합 
    for j in list(combinations(range(10),i)):
        decrease_Number = ""
        for k in sorted(j, reverse = True):
            decrease_Number += str(k)
        answer.append(int(decrease_Number))

answer.sort()

if(n >= len(answer)):
    print(-1)
else:
    print(answer[n])