[BOJ] 2624 - 동전 바꿔주기 (Python, JavaScript)

 

 

아이디어

 

동적 계획법으로 각 동전을 사용한 교환 방법의 가짓수를 저장해 나간다.

 

 

풀이 #1 (Python)

 

0으로 채워진 T+1 크기의 리스트 dp를 생성하는데, dp[i]에는 i원의 교환 방법 가짓수를 저장한다.

for문에서 동전의 금액 p와 동전 개수 n을 입력 받고, temp에 리스트 dp를 복사하여 저장한다.

 

p원 동전으로만 교환하는 방법의 가짓수는 1이므로 n 이하의 자연수 i에 대해 dp[p*i]를 1씩 증가시킨다.

p원 동전을 사용하여 교환하는 방법의 수는 그 금액보다 p원만큼 작은 금액을 기존 동전들로 교환하는 방법의 수와 같다.

따라서 기존 동전들과 함께 사용하여 교환하는 방법의 수 dp[j]에 기존 동전들로만 교환하는 방법의 수 dp[j-p*i]를 더한다.

 

지폐의 금액 T를 넘는 동전의 금액은 고려하지 않기 위해 break로 빠져 나온다.

 

import sys

input = sys.stdin.readline

def solution():
    T = int(input())
    k = int(input())
    dp = [0]*(T+1)
    for _ in range(k):
        p, n = map(int, input().split())
        temp = dp[:]
        for i in range(1, n+1):
            if p*i > T:
                break
            dp[p*i] += 1
            for j in range(p*i+1, T+1):
                dp[j] += temp[j-p*i]
    print(dp[-1])

solution()

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 마찬가지 방식으로 동작한다.

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

const T = +input[0];
const K = +input[1];
let dp = Array(T+1).fill(0);
for (let k=2; k<K+2; k++) {
    const [p, n] = input[k].split(' ').map(Number);
    const temp = [...dp];
    for (let i=1; i<=n; i++) {
        if (p*i > T) break;
        dp[p*i] += 1;
        for (let j=p*i+1; j<=T; j++) dp[j] += temp[j-p*i];
    }
}
console.log(dp[T]);