2293 동전1

문제

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.

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

입력

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

출력

첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다.

====

문제 분석

기존의 동전을 조합해서 k원을 만드는 경우의 수를 구하는 문제에서는 점화식 dp[i] = dp[i]+dp[i-coin]를 통하면 구할 수 있었다.

해당 문제에서 생기는 특이점은 동일한 숫자 조합은 같은 경우의 수로 봐서 배제해야한다는 것이다. 이 특이점을 해결하기 위해선 기존 점화식과 더불어 규칙을 만들면 됐다.

1,2,5 동전이 있다면 

1 -> (1)

2 -> (1,1) (2)

3->(1,1,1)(1,2)

4=> (1,1,1,1)(1,1,2)(2,2)

5=>(1,1,1,1)(1,1,1,2)(1,2,2)(5)

위에서 보았듯 숫자 조합을 오름차순으로으로만 만들면 되는 것이다.

하지만 이것을 위해 숫자들의 조합을 일일히 할 필요 없이 동전을 오름차순으로 정렬한 뒤 첫번째 동전으로만 만들 수 있는 최대한의 금액 조합을 만들고, 그 뒤 동전부터도 최대한의 금액 조합에 현재의 동전을 넣어주면 된다.

예를 들어, 동전 1원만으로 4원을 만들 수 있느 경우는 1,1,1,1 이다

이후 동전 2원까지 합세하여 만드는 경우는 4원-2원 = 2원의 조합에 2원을 추가해주면 된다는 것이다. --> (1,1,2) (2,2)

이것을 점화식으로 만들면 

dp[currentCoin] += dp[currentCoin - coin];

동전 첫 순서부터 금액 1~k원까지 반복문을 만든다.

for (let i = 0; i < n; i++) {
        const coin = coins[i];
        for (let currentCoin = 1; currentCoin <= k; currentCoin++) {
            if (currentCoin - coin < 0) continue;
            else {
                dp[currentCoin] += dp[currentCoin - coin];
            }
        }
}

정답코드

자바스크립트 정답 코드는 아래와 같은데 문제 이슈를 보니 node.js로 제출하면 뭔 짓을 하든 메모리 초과가 뜬다고 한다.

그래서 파이썬으로 변행해서 제출했더니 정답 됨

const main = (n, k, coins) => {
    const dp = Array.from({ length: k + 1 }).fill(0);
    dp[0] = 1;
    coins.sort((a, b) => a - b);

    for (let i = 0; i < n; i++) {
        const coin = coins[i];
        for (let currentCoin = 1; currentCoin <= k; currentCoin++) {
            if (currentCoin - coin < 0) continue;
            else {
                dp[currentCoin] += dp[currentCoin - coin];
            }
        }
    }
    console.log(dp);
};
const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const [n, k] = input[0].split(' ').map((v) => +v);
const coin = [];
for (let i = 1; i < n + 1; i++) {
    coin.push(+input[i]);
}

main(n, k, coin);

 

def main(n, k, coins):
    dp = [0] * (k + 1)
    dp[0] = 1
    coins.sort()

    for coin in coins:
        for current_coin in range(1, k + 1):
            if current_coin - coin >= 0:
                dp[current_coin] += dp[current_coin - coin]

    print(dp[k])

if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().strip().split("\n")

    n, k = map(int, data[0].split())
    coins = list(map(int, data[1:]))

    main(n, k, coins)