효율적인 화폐 구성

이 문제는 2로 먼저 2,4,6,8값을 1씩 더하면서 올리고, 3으로 그다음을 올리면서 겹치는 부분은 d-3과 d-2의 값을 비교해서 풀 수 있다. 그리고 화폐를 최소한으로 하는 것이기 때문에 최대한 값이 큰것으로 먼저 나눠지면 몫을 저장해서 출력하고, 만약 나눠지지 않는다면 2씩 계속 빼는 방법이 있다. 왜 가장 큰값부터 먼저 나눠주냐면 어쩔 수 없이 큰 값부터 나누는 게 최소한의 값일 수 밖에 없다. 예를 들어 a+b = 18라는 값이 있다고 해보자. a가 b보다 클때 a의 값을 최대한으로 많이 넣으면서 등식이 성립해야한다. 그러기 위해서는 b를 조금씩 올리면서 a가 나눠지는 값이 되었을 때 가장 큰 값이 되는 것이다. 만약 2씩 계속 빼다가 나눠지지 않는다면? 그 수는 절대로 만들어질 수 없는 수인 것이다. 8이 있을 때 2와 5로 만들어본다고 하자. 5를 먼저 나눴는데 나눠지지 않아서 2를 빼고 또 반복해서 4,2,0이 된다. 아 정정한다. 2로 빼다가 0이 되지 않는다면 만들어지지 않는 수 인 것이다. 코드를 통해 알아보자.

 

1. 1번 방법

n,m = map(int,input().split())

array = []

for i in range(n):
  array.append(int(input()))

d = [10001] * (m+1)

d[0] =0

for i in range(n):
  for j  in range(array[i], m+1):
    if d[j-array[i]] != 10001:
      d[j] = min(d[j], d[j-array[i]]+1)


if d[m] == 10001:
  print(-1)
else :
  print(d[m])

 

 

2. 2번 방법

아 2번 방법은 안된다. 백준의 설탕문제와 비교했을 때 설탕문제는 변수가 2개였기에 가능한 것이였다. 이건 변수가 100개 까지 될 수 있으니 하나하나 하면 굉장히 비효율적이다. 위 방식으로 문제를 해결하자.