[다이나믹 프로그래밍] 효율적인 화폐 구성

n가지 종류의 화폐를 사용해 m원을 만드는 최소한의 가지수를 출력하는 문제.

 

 

 

 

 

 

나의 코드

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

coin=[]
for i in range(n):
    coin.append(int(input()))

dy=[10001]*(m+1)
dy[0]=0
for i in range(n):
    for j in range(coin[i],m+1):
        dy[j]=min(dy[j],dy[j-coin[i]]+1)

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

이번에도 문제를 풀지 못했다..

30분 가량 끙끙된 이후 분명 이전에 봤던 문제 같아 인터넷 서칭을 해보니 이전에 봤던 유형이 맞았다..!

초반 dp테이블값을 0으로 모두 고정을 하고 접근을 하려다 보니 막혔던것이 었다..

 

결국 해결점은 인덱스 0을 제외한 모든 값들을 최대값으로 세팅한 뒤 로직을 구성하면 깔끔하게 짧고 가독성 좋은 코드가 완성이 된다..!
처음 접한 문제는 정말 길이 보이지 않는다..

우선..다이나믹 프로그래밍 여러 유형들을 접한 이후 더 깊은 고민을 해야 겠다.

 

 

정답 코드

# 정수 N, M을 입력 받기
n, m = map(int, input().split())
# N개의 화폐 단위 정보를 입력 받기
array = []
for i in range(n):
    array.append(int(input()))

# 한 번 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [10001] * (m + 1)

# 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
d[0] = 0
for i in range(n):
    for j in range(array[i], m + 1):
        if d[j - array[i]] != 10001: # (i - k)원을 만드는 방법이 존재하는 경우
            d[j] = min(d[j], d[j - array[i]] + 1)

# 계산된 결과 출력
if d[m] == 10001: # 최종적으로 M원을 만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

나의 풀이와 완전히 같다 !