[알고리즘] 만들 수 없는 금액

문제  (이코테 P. 314)

동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

예를 들어, N=5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다.

또 다른 예시로, N=3이고, 각 동전이 각각 3원, 5원, 7원 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다.

 

입력

첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. (1 <= N <= 1,000)

둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어지며 각 자연수는 공백으로 구분된다. 각 화폐 단위는 1,000,000 이하의 자연수이다.

 

출력

첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력한다.

 

---

풀이

전형적인 그리디 문제이다. 주어진 금액을 오름차순으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target 을 업데이터 하는 방법으로 최적의 해를 구할 수 있다.

 

나는 possessed 변수와 target 변수를 이용해서 문제를 풀이했는데, possessed 변수는 '~까지 생성가능한 금액'을 나타낸다. 예를들어 possessed = 5이라면, 5까지의 금액을 생성할 수 있으며 주어진 돈으로 1원, 2원, 3원, 4원, 그리고 5원을 만들수 있다는 말이다.

 

그리고 target변수는 만들수있을지 확인해야하는 금액이다. possessed가 5라면 target은 6이된다. 문제에서 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 원했다. 그래서 5까지의 금액이 생성된다면 다음으로 금액 6도 생성되는지 확인해야된다.

 

금액을 1부터 시작해서 차례로 증가시키며 금액을 확인해야하는데, 정렬된 리스트 맨앞에 1이 없다면 1원은 만들 수 없으므로, 그 경우 1을 반환하도록 했다. 그 다음으로 반복문을 사용하면서 target값을 갱신시키며 확인하는 과정을 거쳤는데, 새로 확인하는 값이 target값보다크다면 target은 절대 만들 수 없다. 그때 target을 반환해주면 된다.

 

예를들어, 만들수 있는 금액(possessed)이 5원까지이면 target은 6이다. 직후에 새로 들어온 금액이 5라면, 1원부터 10원까지 생성하는 것이 가능하다 (새로 들어온값 5 + 생성할수 있는값 5). 이때는 target이 11로 갱신된다. 그리고 새로들어온 금액이 6이라면, 1원부터 11원까지 생성하는 것이 가능하다 (새로 들어온값 6 + 생성할수 있는값 5). 이때는 target이 12로 갱신된다. 그러나, 새로 들어온 값이 7이라면 6원을 생성하는것이 불가능하다. '새로 들어온값 + 생성할 수 있는값' 으로 6원을 만들지 못하기 때문이다. 따라서, 새로 확인하는 값이 target 값보다 크다면 target값을 만들 수 없다. 이때 target값을 반환해주면 된다.

 

target값을 만들 수 있다면, 소유할수있는 금액(possesed)을 업데이트해주고 다시 위 과정을 반복한다.

 

#1) n개의 동전
#2) n개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값
#3) 각 동전은 무한히 주어지지는 않음

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


def find_impossible_min_value():	
	# 만들수 없는 양의 정수 금액
	if money[0] != 1:
		return 1
	# possessed: ~까지 생성가능한 금액
	possessed = 1
	
	for new in money[1:]:
		# 다음에 생성해야할 금액(소유금액보다 1원높은 금액)
		target = possessed + 1

		# 새로 들어온 값에 의해 생성될수 없는 값이 있다면 반환
		if new > target:
			return target
		# target값을 만들수 있는경우 >> 소유가능 금액 갱신
		else:
			possessed += new
		

print(find_impossible_min_value())