백준 동전2 2294 DP

이전과 동전과 달라진 점

이전에 풀었던 9084 동전처럼 memo를 만들어보자.
그러면 반복문에서 각 회차의 동전으로 만들 수 있는 memo 배열을 확인할 수 있는데 5원이 주어졌을 때 15원을 모든 방법들 중 최소한의 동전 개수인 3개의 5원을 써서 만들 수 있다. 그러므로, 기존에 memo로 방법 가지 수를 셌던 방법을 변형하자.

import sys
input = sys.stdin.readline

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

# memoization
memo = [0] * (k + 1)
memo[0] = 1 # 금액 범위 1~10000 초기화

for _ in range(n):
    coin = int(input())
    for i in range(coin, k + 1):
            memo[i] += memo[i - coin]

print -1 if memo[k] == 0 else memo[k]

1트 (80% 정도에서 틀렸습니다!)

이전에는 메모배열 인덱스를 금액으로 하고 값을 금액을 달성하는 방법의 가지수로 저장했다면, 이번에는 값에 해당 인덱스에 도달하기 위해 사용한 동전의 개수를 저장한다.

k = 15로 주어졌다면

• 사용한 동전이 1원일 때,
  memo[15] = 1*15
• 사용한 동전이 5원일 때,
  memo[15] = 5,5,5
• 사용한 동전이 12원일 때,
  memo[15] = 12, 1, 1, 1

5원을 3번 사용하면 최소 사용으로 15원을 만들 수 있다. 이 과정을 뜯어보면 coin=5일때 memo[5] = 1 , memo[10]=2, memo[15]=3이 되어야 한다.

이건 각 동전마다 k에 도달하기 위해 사용한 동전 개수를 메모해두고, min 함수로 coin개수 때부터 비교해서 찾아낼 수 있다.

2트 (성공)

1트에서도 최소값을 대조해야했는데 0으로 초기화했어서 틀린거라 보면 된다

import sys
input = sys.stdin.readline

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

# memoization
memo = [10001] * (k + 1) # 최소값 비교를 위해 적당히 큰 수로 초기화
memo[0] = 0 # 0원이 되기위해 쓰는 동전 개수는 0개
ans = [] # min을 출력하기 위한 배열

for _ in range(n):
    coin = int(input())
    for i in range(coin, k + 1):
            memo[i] = min(memo[i-coin]+1, memo[i])

print(-1 if memo[k] == 10001 else memo[k])