[백준]1082 방번호 #그리디

1. 풀이

(1) 가장 큰 숫자를 만들기 위해선 최대한 많은 자릿수를 확보해야한다.

=> 최대한 많은 숫자를 사기 위해서 가장 싼 숫자를 구매한다

(pick=[a,b,c,d] => d*1000+c*100+b*10+a를 나타낸다)

(2) 가장 큰 자릿수 부터 큰 숫자로 바꿀 수 있는지 (남은돈)과 (바꿀때 드는 차액)을 비교한다.

=> pick에 가장 오른쪽 원소부터 가장 큰 숫자에서 하나씩 작은 숫자로 내려오며 확인한다.

​

*예외

(1) 0이 가장 싼 경우가 있다. 이경우 시작숫자가 0000...이된다(pick=[0,0,0,0...])

이때 0을 산다고 돈을 다 쓰고 다른 숫자를 살 수 없으면, 숫자를 만들 수가 없다.

따라서 그 경우(0만있고 다른숫자를 살 수 없는)를 대비해 0을 다시 환불하고 돈을 받아서 0이외의 숫자 구매를 재시도한다.

#모두다 0이면
    if not any(pick):
        pick.pop()
        add(remainMoney+L[0],digit-1)

(2) 0을 다 팔았는데도 다른 숫자를 살 수 없으면 답이 0이 되는 경우이다. (이 예외를 처리해주지 않아서 비어있는 pick에 pop()을 해서 런타임에러가 났다)

#위에 코드에 추가
        if not pick:
            print(0)
            sys.exit()

 

2. 소스코드

import sys
from collections import deque

N=int(input())
L=list(map(int,input().split()))
money=int(input())

minCost=min(L)
minNum=L.index(minCost)
if N==1:
    print(0)
    sys.exit()

#digit 자리수 검사해야함
def add(remainMoney,digit):
    #print(remainCost,pick)
    #가장 큰 오른쪽 숫자부터 가장 큰거 넣어보기
    for i in range(digit,-1,-1):
        if pick[i]!=N-1:
            #큰거부터 넣어봄
            for j in range(N-1,pick[i],-1):
                nowCost=L[j]-L[pick[i]]
                if nowCost<=remainMoney:
                    pick[i]=j
                    add(remainMoney-nowCost,digit-1)
                    return
    #모두다 0이면
    if not any(pick):
        if not pick:
            print(0)
            sys.exit()
        pick.pop()
        add(remainMoney+L[0],digit-1)

num=money//minCost
pick=[minNum for i in range(num)]
cost=num*minCost
add(money-cost,num-1)
ans=0
for i in range(len(pick)):
    ans+=(10**i)*pick[i]
print(ans)