백준 1082 방 번호 python

DFS를 이용해서 가진 돈으로 만들 수 있는 번호의 조합을 찾는다.
단, 단순히 모든 조합을 찾는다면 시간초과가 나오니 백트래킹을 적용해서 시간을 줄여야 한다.

📜 문제 바로 가기 : 방 번호

제출코드

파이썬

import sys
input = sys.stdin.readline

N = int(input())
price = list(map(int, input().split()))
M = int(input())

maxLength = 1
minPrice = min(price)
if N > 1 and M - min(price[1:]) >= 0:
    maxLength += (M - min(price[1:])) // minPrice

ans = -1

def recur(s, MAX, money, number):
    global ans
    if ans != -1 or (s >= 1 and s + (money // minPrice) != maxLength):
        return

    if s == maxLength:
        ans = int(number)
        return

    for i in range(MAX, -1, -1):
        if price[i] <= money:
            recur(s+1, i, money-price[i], number+str(i))

recur(0, N-1, M, "")
print(max(0, ans))

---

접근방법

백트래킹 1번 숫자 자리 수 구하기

우리의 목표는 가장 큰 수를 만드는 것이다.
수를 가장 크게 만들려면 자리수가 커야한다. 이게 1순위다.

난 가진 돈으로 만들 수 있는 최대 자리수를 구해 maxLength에 저장했다.
그리고 함수를 시작하기 현재 가진 돈으로 maxLength를 만들 수 있는지 확인한다.
돈을 더 써서 maxLength를 만들 수 없다면 함수를 종료한다.

백트래킹 2번 큰 수부터 확인하기

함수의 종료 조건은 maxLength를 완성하면 종료한다.

이때 가장 큰 수 N-1부터 사용해 보는 방법이다.
같은 자리수라면 큰 수를 사용했을 수록 숫자가 더 큰건 당연함으로 이 방법으로 maxLength를 만들었다면 그 수가 가장 큰 수가 되는 것이다.

즉, maxLength를 달성한 처음 수를 ans에 넣어 놓고 함수 종료조건에 if ans != -1을 추가하여 값이 한번이라도 만들어지만 함수를 더 이상 실행하지 않도록한다.