[백준][DP] 동전 2

동전 2

 

 

• 첫 풀이

coin을 정렬한 뒤에 나눠서 갯수를 세는 식으로 하면 O(nlogn) 이 되지 않을까? 해서 진행했다가 
    - 정렬: O(nlogn)
    - 나눗셈 반복: O(n)
나눗셈 방식은 탐욕적 접근법(Greedy Algorithm)이고, 항상 최적해를 보장하지 않는다
모든 경우를 확인하는 완전탐색(DFS)이나 최적해를 보장하는 DP를 사용해야 함
⇒  시간이 O(nlogn)보다 훨씬 커질 수 있음.

• • 도중에 나눠서 갯수를 세면 무조건 최대공약수 갯수만큼 사용하게 된다는 것을 깨닫고
  • 나누지 않고 빼는 식으로 진행 → 당연히 시간초과
  • ⇒ dfs 코드를 수정해서 dp로 변경하기로 결정

n,k=map(int,input().split())
coins=sorted([int(input()) for _ in range(n)])
answer=float('inf')
def dfs(num,cnt):
    global answer
    if num==0:
        answer=min(answer,cnt)
        return

    for coin in coins:
        if num<coin:
            continue
        dfs(num-coin,cnt+1)

dfs(k,0)
if answer==float('inf'):
    print(-1)
else:
    print(answer)

 

 

• 다음 풀이
  • 위 dfs 코드를 바탕으로 dp 탑다운 방식으로 수정
  • sys.setrecursionlimit(10000): 파이썬의 기본 재귀 한도를 1,000에서 10,000으로 증가
    • 이거 없으면 런타임 에러 남
  • dp[i]: 금액 i를 만들기 위해 필요한 최소 동전 수
  • num < 0:
    • num이 0보다 작아지면 유효하지 않은 경우 ⇒ float('inf')를 반환
  • dp[num] != -1
    • 앞에서 이미 계산 된 경우 ⇒ 바로 반환(메모이제이션)
  • num을 만들기 위한 최소 동전 수를 계산해서 저장

import sys
sys.setrecursionlimit(10000)

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

dp = [-1] * (k + 1)
dp[0]=0

def dfs(num):
    if num < 0:
        return float('inf')

    if dp[num] != -1:
        return dp[num]

    tmp = float('inf')
    for coin in coins:
        tmp = min(tmp, dfs(num - coin) + 1)

    dp[num] = tmp
    return dp[num]

answer = dfs(k)
if answer == float('inf'):
    print(-1)
else:
    print(answer)

 

• 다른 사람 풀이
  • 바텀업
  • dp[i]: 금액 i를 만들기 위해 필요한 최소 동전 수
    • dp[i] = 10001: 초기값으로 매우 큰 값(10001)을 설정하여, 금액을 만들 수 없는 경우와 구분
  • 동전을 사용해서 금액을 만들 수 없는 경우를 10001(min)로 유지

for num in li: # 각 동전 금액에 대해
    for i in range(num, k+1): # 해당 동전 금액부터 목표 금액까지 확인
        dp[i] = min(dp[i], dp[i-num] + 1)

# 동전의 개수 n, 목표 금액 k
n, k = map(int, input().split())

coins = []
for _ in range(n):
    coins.append(int(input()))

# dp[i]: 금액 i를 만들기 위한 최소 동전 개수
dp = [10001] * (k + 1)
dp[0] = 0

for coin in coins:  # 각 동전에 대해
    for i in range(coin, k + 1):  # 해당 동전으로 만들 수 있는 금액부터 시작
        dp[i] = min(dp[i], dp[i - coin] + 1)

if dp[k] == 10001:  # 목표 금액 k를 만들 수 없는 경우
    print(-1)
else:
    print(dp[k])