접근

이 문제를 보고 처음에는 저번에 풀었던 거스름돈 문제랑 비슷하다고 느꼈다. 그떄는 그리디로 풀었던 기억이 있어서 우선 그리디로 접근해보았다.

시도

def try_1():

	n, m = map(int, input().split())
	coins = []
	for _ in range(n):
		coins.append(int(sys.stdin.readline().rstrip()))

	coins.sort(reverse=True)
	count = 0

	for i in coins:
		count += m // i
		m = m % i
		if m == 0:
			return count
	return -1

예시에 나온 테스트케이스는 답이 맞아서 일단 해설을 보기로 했지만 뭔가 조건이 부족하다는 느낌이 강하게 들었다. 그래도 일단은 해설을 보면서 배우기로 했다.

해설

def solution():

	n, m = map(int, input().split())
	coins = []
	for _ in range(n):
		coins.append(int(sys.stdin.readline().rstrip()))
	
	d = [10001] * (m + 1)
	for i in coins:
		d[0] = 0
		for j in range(i, m + 1):
			if d[j - i] != 10001:
				d[j] = min(d[j], d[j - i] + 1)
	if d[m] == 10001:
		print(-1)
	else:
		print(d[m])

역시나 제출했던 코드는 틀렸었다. 단순히 그리디로 접근하는 문제가 아니였다. 이 문제도 다이나믹 프로그래밍으로 푸는 문제였는데 우선 m 의 크기만큼 배열을 선언했고 그 사이에 있는 모든 금액에 대한 최소 화폐를 넣기 위해서 우선 올 수 있는 가장 큰 값인 10000 보다 높은 10001을 배열 안에 전부 넣어주었고 앞으로 오는 값을 넣어주고 min 으로 비교하여 최소값을 넣는 방식으로 진행된다.

내가 해설을 한번 간단하게 보고 스스로 다시 짜보았지만 틀렸었는데 그 이유는 놓친점이 몇가지 있어서였다. 처음에는 단순히 동전의 배수 만큼(예를 들어서 2원 동전이 오면 2, 4, 6, 8..) 이런식으로 값을 1씩 늘려서 넣어주면 끝나는 줄 알았다. 하지만 만약에 동전이 (2, 3, 5) 이렇게 있으면 7 에는 아무 값도 안들어가는 경우가 생겼다.

따라서 이를 해결하기 위해서는 주어진 동전의 값부터 m 값 까지 도는 반복문을 넣어줘야 한다. 예를 들어서 2원 동전이 오면 2원부터 m 원까지, 5원 동전이 오면 5원 부터 m 원 까지.. 이렇게 반복문을 돌면서 확인하는 값을 j 라고 하면 만약 d[j - coin]의 값이 10001 이 아니면(즉, 값이 들어간 적이 있으면) d[j] = min(d[j], d[j - coin] + 1)울 해주는 방식이다.

이렇게 하면 동전으로 만들 수 있는 모든 경우의 수에 값이 들어가게 된다.