📎 문제 링크

n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.

사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.

📎 입력

첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.

📎 출력

첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.

📎 오답코드

• 시간초과 발생

import sys

n, k = map(int, sys.stdin.readline().split())

coins = sorted(list(set(list(int(sys.stdin.readline().strip()) for _ in range(n)))), reverse=True)
m = len(coins)
 
ans = 1e9

def dfs(turn, cnt, total):
    global ans

    if total > k:
        return
    
    if cnt >= ans:
        return
    
    if total == k:
        ans = min(ans, cnt)
        return
    
    if turn >= m:
        return
    
    
    for i in range(turn, m):
        dfs(i, cnt + 1, total + coins[i])
    
dfs(0, 0, 0)

if ans == 1e9:
    print(-1)
else:
    print(ans)

📌 답안

• DP 사용

import sys

n, k = map(int, sys.stdin.readline().split())

coins = sorted([int(sys.stdin.readline().strip()) for _ in range(n)])
m = len(coins)

# dp 배열 초기화
dp = [float('inf')] * (k + 1)
dp[0] = 0

# 동전 값을 하나씩 확인하며 dp 배열 갱신
for coin in coins:
    for i in range(coin, k + 1):
        dp[i] = min(dp[i], dp[i - coin] + 1)

if dp[k] == float('inf'):
    print(-1)
else:
    print(dp[k])

• 동전 값들을 오름차순으로 정렬한 후, dp 배열을 초기화합니다.
• 각 동전 값을 하나씩 확인하며 dp 배열을 갱신합니다.
• 🔥 dp[i]는 합이 i가 되도록 동전을 사용했을 때 필요한 동전의 최소 개수를 나타냅니다.
• 이전 동전들의 결과를 활용하여 dp 배열을 갱신하므로, 중복 계산을 피할 수 있습니다.
• 마지막으로 dp[k] 값을 출력합니다.

➡ 동전의 개수에 상관없이 입력 크기에 비례하여 시간이 소요