[백준] 18511번 큰 수 구성하기

💡문제접근

• 백트래킹 알고리즘으로 문제를 접근해서 여러 개의 테스트케이스가 통과되었지만 일부 코너 케이스로 인해서 WA를 받았고 결국 최후의 방법인 itertools를 이용했다. 백트래킹을 공부한다는 차원에서 백트래킹 코드도 추가하여 포스팅해야겠다.

💡코드(메모리 : 32276KB, 시간 : 52ms)

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

N, K = map(int, input().strip().split())
lst = list(map(int, input().strip().split()))
length = len(str(N))

res = []
while True:
    temp = list(product(lst, repeat = length))
    for i in temp:
        i = int(''.join(map(str, i)))
        if i <= N:
            res.append(i)
    if len(res) >= 1:
        print(max(res))
        break
    else:
        length -= 1

💡소요시간 : 1h