[백준 9084번] 동전 (python/파이썬) + 실버 II 달성

그리디로 못푸는 문제이길래 DP인줄 알고 짰다가

DP도 아니구나 싶어서 DFS 비슷하게 풀었다가 시간초과가 떠서

DFS + DP로 성공

 

🌼 문제 링크

https://www.acmicpc.net/problem/9084

9084번: 동전

• 티어:  골드 V
• 분류: 다이나믹 프로그래밍

 

 

❗ TRIAL 1.

코드

def solution(N, coins, target):
    c = coins.pop() #largest
    
    if N == 1:
        if target % c == 0:
            ans = 1
        else:
            ans = 0
    else:        
        ans = 0
        for i in range(target//c + 1):
            ans += solution(N-1, coins, target-c*i)

    coins.append(c)
    return ans
    

T = int(input()) #num of test cases
for _ in range(T):
    N = int(input()) #num of coins
    coins = list(map(int, input().split())) #coins in ascending order
    M = int(input()) #target price

    print(solution(N, coins, M))

 

코드 설명

 

- 가장 큰 coin단위부터 순차적으로 모든 경우의 수에 대해 검사.

- 남은 금액을 나머지 coin으로 만들 수 있는 경우의 수를 계산해서 더한 후 return

 

틀린 원인

 

시간초과. 같은 coins로 target을 만드는 계산이 여러번 등장하므로 여기에 중간결과를 저장하는 DP를 추가해야 함.

 

💡 Solution

코드

from collections import defaultdict

def solution(d, N, coins, target):
    if target == 0:
        return 1
        
    c = coins.pop() #largest
    
    if N == 1:
        if target % c == 0:
            ans = 1
        else:
            ans = 0
    else:
        key = ' '.join(map(str, [target]+coins))
        if d[key] is None:
            ans = 0
            for i in range(target//c + 1):
                ans += solution(d, N-1, coins, target-c*i)
            d[key] = ans
        else:
            ans = d[key]

    coins.append(c)
    return ans
    

T = int(input()) #num of test cases
for _ in range(T):
    N = int(input()) #num of coins
    coins = list(map(int, input().split())) #coins in ascending order
    M = int(input()) #target price

    d = defaultdict(lambda: None)
    print(solution(d, N, coins, M))

 

코드 설명

• DFS + DP
• 가장 큰 coin단위부터 순차적으로 모든 경우의 수에 대해 검사.
• 남은 금액을 나머지 coin으로 만들 수 있는 경우의 수를 계산해서 더한 후 return
• 특정 coin들로 특정 target을 만드는 계산이 여러번 등장하므로 이를 저장하는 dp를 추가한다.
  • target + coin을 문자열로 만들어 dp의 key로 사용했다.

 

 

더 나은 풀이

• 풀이1: DP bottom-up
  
  • coin을 하나씩 순회하면서,
    • 0부터 target까지의 모든 금액에 대해
      • 현재 coin을 뺀 금액에 대한 경우의 수를 더한다.

 

for c in coins:
	for i in range(c, target+1):
	    d[i] += d[i-coin]
        
print(d[target])

 

 

실버 II 달성 😊

•