만들 수 없는 금액

출처:: k 대회 기출

분류:: 그리디

 

1. 문제 이해 및 해결과정

1. 첫번째 풀이 1) 동전 오름차순 정렬 후  2) 모든 경우 다해보고 나온 sum을 set에 넣음 3) 1부터 차례대로 인덱스와 값이 다른 지점의 인덱스가 만들 수 없는 최소값이다  => n이 1000이므로 2^1000 이되어 시간초과가 날 수 밖에 없다. 2. 그리디 - 거스름돈 문제는 각 화폐 단위마다 무한 개의 동전이 존재한다고 가정했는데, 이 문제에서는 동전의 수가 한정적이라는 점이 다르다  - 동전을 화폐 단위 기준으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target변수를 업데이트 하는 방법으로 최적의 해를 계산할 수 있다. ex) 1 2 3 8   네 개의 동전이 있다고 가정  1) 처음에는 금액 1을 만들 수 있는 지 확인하기 위해 target=1로 설정  2) target = 1을 만족하는 지 확인 , 화폐 1이 있다. 이어서 target을 1+1=2로 업데이트 한다 = 1까지의 모든 금액을 만들 수 있다  3) target=2를 만족하는지 확인한다. 화폐 2인 동전이 있다. 따라서 target은 2+2=4로 업데이트 한다 = 3까지의 모든 금액을 만들 수 있다  4) target=4를 만족하는지 확인, 화폐 단위가 3인 동전이 있다. target=4+3=7이 된다 =6까지의 모든 금액 만들 수 있음  5) target=7을 만족하는지 확인 , 화폐 8인 동전이 있다. 7을 만드는 방법이 없다. => 정답은 7

 

 

2. 풀이방법

 

3. 오답원인

 1. 시간초과

#만들 수 없는 금액
#
'''
5
3 2 1 1 9
'''
import sys
sys.stdin = open("input.txt","r")

n=int(input())
coin=list(map(int,input().split()))
coin.sort()
tmp=set()

def DFS(i,sum):
    tmp.add(sum)
    if i==len(coin):
        return
    else:
        DFS(i+1,coin[i]+sum)
        DFS(i+1,sum)

DFS(0,0)

table=list(tmp)

for i in range(0,len(table)):
    if i!=table[i]:
        print(i)
        break

- 리스트를 오름차순 정렬하기, 1부터 되는 값을 확인해보기 라는 아이디어는 생각했지만 더 이상의 아이디어가 떠오르지 않았다.

 

4. 알게된 점

 set()은 요소에 직접 접근할 수 없다

=> set을 리스트로 바꾸어 해결하였다.