본문 바로가기
알고리즘

[백준/파이썬] #1174

by 룰루루 2025. 4. 7.

문제집에서 보고 푼 문제라 백트래킹이라는 힌트를 보고 시작했다. 그런데 암만 봐도 백트래킹으로 접근하는 방법이 생각나지 않았다. 힌트로 '브루트 포스'가 있길래 해당 방법을 시도해봤다. 

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