책 314p

문제

• 시간 제한
  • 1초
• 입력
  • 첫째줄에는 동전의 갯수 나타내는 N (1<=N<=1,000)
  • 둘째줄에는 각 동전의 화폐단위를 나타내는 N개 자연수 (각 화폐단위는 1,000,000 이하의 자연수)
• 출력
  • 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력

N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하시오.

예시) N=5, [3,2,1,1,9] 원의 동전이 있을때,
만들 수 없는 양의 정수 금액 중 최솟값은 8원

풀이방법

처음 든 생각

브루트 포스로 $nCr$만큼 모든 조합을 계산할까?

안되는 이유 -> $nCr$ 의 경우, 조합의 갯수 r이 n보다 작아야하는데
동전이 n보다 더 많이 더해질 수도 있다.
그렇게 벗어나는 값을 확인할 수 없다.

풀이 아이디어

1. 오름차순으로 정렬
   2.1부터 차례대로 특정한 금액 만들 수 있는지 확인

예시) [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

풀이 코드

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for x in data: 
	# 만들 수 없는 금액을 찾았을 때 반복 종료
	if target < x :
		break
	target += x

# 만들 수 없는 금액 ㅜㄹ력
print(target)

느낀점

• 이게 왜 최적을 보장하지? 라는 의문
  풀어 말하면 [이전의 가능한 범위] + [새로 포함시키는 동전] = [새로운 가능한 범위] 가 어떻게 가능한거지?
  • 일단
    이걸 왜 단정할 수 있는지 납득이 안됐음.
  • 만약 [1,2,3,5] 이 있으면 1부터 6까지 만들 수 있다고 체크했다고 생각하자 (동전 1,2,3 까지 포함 완료)
    • 1원 = 1
    • 2원 = 2
    • 3원 = 3
    • 4원 = 1+3
    • 5원 = 2+3
    • 6원 = 1+2+3
  • 금액 5를 포함시키면, 6+5=11 까지의 금액을 만들 수 있다.
    다음과 같다.
    
    이렇게 5가 더해질뿐, 이전의 패턴이 똑같이 반복되는 것이므로,
    [이전의 가능한 범위] + [새로 포함시키는 동전] = [새로운 가능한 범위] 가 가능하게 된다.

오호라~ 글쿤 다시 풀자 외우자 ㅎㅎ