[백준] 동전1 (2293번) - Python / 알고리즘

✅문제 - 동전1 (2293번) 

---

 

✅필요 알고리즘 개념 - DP

---

🔵DP의 적용

◼ 모든 동전의 가격을 고려하며 dp를 만들면 경우의 수가 복잡하므로 동전의 종류를 1개씩 늘려간다.

◼ 처음에는 가장 저렴한 동전 1개만 사용하여 dp를 만든다. (예제 입력의 경우 가치가 1인 동전을 사용한다.)

동전의 가치가 1인 경우 DP는 위의 표와 같다. 위의 표는 동전의 가치가 1인 동전만을 사용해 k원을 만든 것이다.

◼ 동전의 가치가 2인 경우를 dp에 추가하자

현재 dp[n]은 n원을 1원짜리 동전으로 만들 때의 경우의 수이다.

2원 짜리 동전을 사용하게 되면 (1) 1원짜리 동전으로만 경우의 수를 만든 경우와 (2) 2원짜리 동전도 사용한 경우의 수가 있다.

위의 (1)의 경우의 수가 dp[n] 이고 (2)의 경우는 dp[n-2]가 된다.

그러므로 dp[n] += dp[n-2] 가 된다.

 

◼ 위의 행위를 모든 동전의 행위에 대해서 진행하면 된다.

 

✅코드

---

import sys

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

coins = []

for _ in range(n):
    coins.append(int(sys.stdin.readline().rstrip()))

coins.sort()

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

# 첫 번째 동전으로 dp 세팅
for i in range(k//coins[0]+1):
    dp[i*coins[0]] = 1

# 두 번째 동전부터 dp를 계속 갱신해나감
for i in range(1,n):
    # 동전의 가치부터 시작하면 되므로 시작점이 coins[i]
    for j in range(coins[i],k+1):
        dp[j] += dp[j-coins[i]]

print(dp[k])