다이나믹 프로그래밍 기법
한 번 해결된 부분 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 문제 해결 기법.

탑다운 방식
재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
바텀업 방식
반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결하는 방식

✅ 문제

N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 회폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.
불가능할 때는 -1을 출력한다.

입력 예시 1

2 15
2
3

출력 예시 1

5

입력 예시 2

2 15
2
3

출력 예시 2

5

💻 코드

N, M = map(int, input().split())

d = [-1] * 10001

money = []

for i in range(N):
    x = int(input())
    money.append(x)
    d[x] = 1
    
for i in range(1, M):
    if d[i] != -1:
        for j in money:
            if d[i + j] == -1:
                d[i + j] = d[i] + 1
            else:
                d[i + j] = min(d[i + j], d[i] + 1)

print(d[M])

설계

리스트 d에 인덱스만큼의 값을 만들 수 있는 화폐의 개수를 저장한다. 처음에 -1로 초기화 하고 화폐가 입력될 때마다 d에 1로 넣어주고 money 리스트 안에 화폐를 넣는다.
리스트 d를 순회하면서 -1이 아니면 입력된 화폐로 만들 수 있는 최소한의 개수를 저장한다.

📝 정리

푸는 데 여러 방법으로 고민 많이 했던 문제이다.
전에는 처음 생각 했던 방법으로 문제를 못풀고 있어도 계속 잡고 있었는데, 이번에 써가면서 푸니까 안 풀리는 방법 말고 다른 방법을 찾아볼 수 있었다.