Daily Algorithm - Day 33

Coin Sums

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).
It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
How many different ways can £2 be made using any number of coins?

영국 화폐 체계에서 동전을 이용해 2£를 만드는 조합의 개수를 구하는 문제이다.

점화식과 배열을 이용해준다면 간단하게 구현이 될 것 같다.

먼저 Java다.

Java

public class Main {
    public static int coinSums(int target, int[] coins) {
        int[] dp = new int[target + 1];
        dp[0] = 1; // 0원을 만드는 방법은 1가지

        for (int coin : coins) {
            for (int i = coin; i <= target; i++) {
                dp[i] += dp[i - coin]; // coin을 추가할 수 있을 때 마다 조합이 늘어난다.
            }
        }

        return dp[target];
    }

    public static void main(String[] args) {
        int target = 200;
        int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};

        System.out.println(coinSums(target, coins));
    }
}

>>> 73682   // correct

다음은 python으로 구현해보자. 크게 달라질 부분은 없어 보인다.

//Python

def coin_Sums(target, coins):
    dp = [0] * (target + 1)
    dp[0] = 1  # 0원을 만드는 방법은 1가지

    for coin in coins:
        for i in range(coin, target + 1):
            dp[i] += dp[i - coin] # coin을 추가할 수 있을 때 마다 조합이 늘어난다.
    
    return dp[target]

target = 200
coins = [1, 2, 5, 10, 20, 50, 100, 200]

print(coin_Sums(target, coins))

>>> 73682   # correct

gpt 선생님도 이 코드에 만족하셨다.

오늘은 여기까지.

-2025.02.11-