코드

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

def solution():

    dp = [0 for _ in range(k+1)]

    # 1 ~ k(목푯값)까지 반복 돌림
    for i in range(1, k+1):
        
        # 경우의 수를 담을 리스트
        tmp = []

        # 주어진 동전을 가지고 반복 실행
        for c in coins:
            
            # i보다 보유한 동전의 값이 더 작고 
            # dp[i-c] : 현재 목표 금액 i에 -c를 한 금액을 만들 수 있는 경우의 수
            # 즉, i-c 금액을 만드는 최소 동전의 개수
            # 이 값이 -1이면 i도 어차피 만들 수 없음
            # 이렇지 않은 경우에만 a에 dp[i-c]의 값 + 1을 추가
            # +1의 이유 =>
            # 이전 까지의 경우의 수(dp[i-c])에 이번 동전(c)를 더 하였으므로 사용한 동전 수가 1개 더 많아짐
            if c <= i and dp[i-c] != -1:
                tmp.append(dp[i-c]+1)

        # a가 비었음 => 주어진 동전으로 목표한 값(i)을 못 만듬
        if not tmp:
            dp[i] = -1

        # 만들 수 있는 경우
        # 가장 작은 경우의 수가 DP 테이블의 값
        else:
            dp[i] = min(tmp)
        
    print(dp[k])
    
solution()

문제 해설

DP 문제 (동전을 가지고 문제를 푸는 유형이 DP나 그리드 알고리즘의 대표적인 유형)

유사 문제 - 동전 1

위 링크의 문제에선 목푯값 k가 되는 모든 경우의 수를 구하였지만, 이 문제의 경우 최소 동전을 사용하여 k를 만들 때, 사용된 동전 개수를 구하라는 문제이다.

핵심은 아래 코드이다.

# 1 ~ k(목푯값)까지 반복 돌림
for i in range(1, k+1):
    # 경우의 수를 담을 리스트
    tmp = []
    
    # 주어진 동전을 가지고 반복 실행
     for c in coins:

        # i보다 보유한 동전의 값이 더 작고 
        # dp[i-c] : 현재 목표 금액 i에 -c를 한 금액을 만들 수 있는 경우의 수
        # 즉, i-c 금액을 만드는 최소 동전의 개수
        # 이 값이 -1이면 i도 어차피 만들 수 없음
        # 이렇지 않은 경우에만 a에 dp[i-c]의 값 + 1을 추가
        # +1의 이유 =>
        # 이전 까지의 경우의 수(dp[i-c])에 이번 동전(c)를 더 하였으므로 사용한 동전 수가 1개 더 많아짐
        if c <= i and dp[i-c] != -1:
            tmp.append(dp[i-c])

목푯값 k까지 반복을 돌려, 1에서 k까지의 금액을 주어진 동전들로 만들 수 있는 경우의 수를 임시 리스트 tmp에 저장한다. 그 후의 로직에서 min(tmp)를 dp테이블에 저장하고 최종적으로 dp[k]를 출력하면 정답이다.

(dp[i-c]의 의미가 쉽게 와닿지 않을 수 있다. 이 의미는 아래와 같다.)

  • i-c원 : 새로운 동전 c를 사용하기 전까지의 금액
  • dp[i] : i원을 만들 수 있는 최소 동전의 개수
  • dp[i-c] c를 사용하기 전까지의 금액을 만들 수 있는 최소 동전의 개수

DP 문제는 많은 사고력과 응용력을 요구한다. 감을 잃지 않도록 꾸준하게 하나씩 풀어야겠다!!!

댓글남기기

참고