문제집에서 보고 푼 문제라 백트래킹이라는 힌트를 보고 시작했다. 그런데 암만 봐도 백트래킹으로 접근하는 방법이 생각나지 않았다. 힌트로 '브루트 포스'가 있길래 해당 방법을 시도해봤다.
import sys
input = sys.stdin.readline
N = int(input())
max_number = 1000000
def is_decreasing(number: int) -> bool:
if number // 10 == 0:
return True
number_string = str(number)
for i in range(len(number_string)-1):
if int(number_string[i]) <= int(number_string[i+1]):
return False
return True
def solution(number: int) -> int:
if number <= 10:
return number-1
current_number = 10
count = 10
while current_number <= max_number:
if is_decreasing(current_number):
count += 1
if count == number:
return current_number
current_number += 1
return -1
print(solution(N))
일단 틀렸다. 시간 초과는 아니었다. 30분이 지났기에 다른 풀이를 참고해서 풀었다. 백트래킹 풀이는 잘 이해가 되지 않아서 조합 풀이를 참고했다.
중간에 combinations(range(0, 10), i) 부분이 처음에는 이해가 잘 안 되어서 print문을 찍어 봤다. 이렇게도 풀리는구나 싶어 신기했다.
import sys
from itertools import combinations
input = sys.stdin.readline
nums = []
N = int(input())
for i in range(1, 11):
for comb in combinations(range(0, 10), i):
comb = list(comb)
comb.sort(reverse=True)
nums.append(int("".join(map(str, comb))))
nums.sort()
try:
print(nums[N-1])
except Exception:
print(-1)
'알고리즘' 카테고리의 다른 글
[백준/파이썬] #16987 (0) | 2025.05.01 |
---|---|
[백준/파이썬] #3980 (0) | 2025.04.28 |
[백준/파이썬] #6443 (0) | 2025.04.05 |
[백준/파이썬] #11657 (0) | 2025.04.04 |
[백준/파이썬] #13549 (0) | 2025.04.01 |