February 3, 2023

2294번: 동전 2

문제 요약

• 각각 가치가 다른 n가지 종류의 동전이 주어졌을 때, 동전을 무한히 사용하여 가치의 합을 k원이 되도록 하는 동전의 최소 갯수
• 1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000
• 시간 제한 1초, 메모리 제한 128MB

풀이

from sys import stdin

input = stdin.readline
n, k = map(int, input().split())
coin_list = [int(input()) for _ in range(n)]
dp = [[-1] * (k + 1) for _ in range(n + 1)]

for coin_count in range(len(coin_list)):
    coin = coin_list[coin_count]
    coin_count = coin_count + 1
    for target in range(k):
        target = target + 1

        if (target / coin == 1):
            dp[coin_count][target] = 1
            continue

        if (dp[coin_count - 1][target] != -1):
            dp[coin_count][target] = dp[coin_count - 1][target]

        if (target - coin > 0 and dp[coin_count][target - coin] != -1):
            if (dp[coin_count][target] == -1):
                dp[coin_count][target] = dp[coin_count][target - coin] + 1
            else:
                dp[coin_count][target] = min(
                    dp[coin_count][target], dp[coin_count][target - coin] + 1)

result = dp[n][k]

print(result)

$dp[i][j] = min(dp[i - 1][j], dp[i][j - coin[i]])$

개선

from sys import stdin

input = stdin.readline
n, k = map(int, input().split())
coin_list = [int(input()) for _ in range(n)]
dp = [0] + [10001] * k

for coin in coin_list:
    for target in range(coin, k + 1):
        dp[target] = min(dp[target], dp[target - coin] + 1)

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

• dp 배열을 1차원으로 변경
• dp의 0번째 요소가 0임을 이용해 조건식을 줄임