[알고리즘][동적계획법] 동전 교환 문제

동전 교환 문제

• 여러 동전의 값 coins = {c1, c2, ... , ck}과 만들어야 하는 목표 액수 n이 주어질때 가장 적은 수의 동전을 사용하여 합이 n이 되도록 하는 문제
• 예를 들어 coins = {1, 2 , 5}이고 n=12라면 최적해는 동전을 3개 사용하여 5 + 5 + 2 = 12입니다.

1. 탐욕법이 실패하는 경우

• 탐욕 알고리즘을 사용하여 문제를 해결하기 위해서 항상 액수가 제일 큰 동전을 택하되, 합이 목표 액수를 넘지 않도록 함
  • 예를 들어 coins = {1, 2, 5}이고 n=12라면 제일 큰 5원짜리 동전 2개를 선택하고 2원짜리 동전 1개를 선택하면 답이 된다.
• coins = {1, 3, 4}, n=6
  • 탐욕 알고리즘 : 4 + 1 + 1 = 6, 동전 3개
  • 반례 : 3 + 3 = 6, 동전 2개

위와 같은 반례를 통하여 동전 교환 문제가 탐욕 알고리즘으로 해결되지 않는 것을 알 수 있습니다.

 

2. 최적해 구하기

• 합 x를 만들기 위한 동전의 최소 개수를 의미하는 함수 solve(x)의 값을 구하기

예를 들어 coins={1, 3, 4}, n=10인경우 solve(0) ~ solve(10)은 다음과 같습니다.

solve(0) = 0
solve(1) = 1
solve(2) = 2
solve(3) = 1
solve(4) = 1
solve(5) = 2
solve(6) = 2
solve(7) = 2
solve(8) = 2
solve(9) = 3
solve(10) = 3

• solve(10) = 3 : 3 + 3 + 4 = 10

 

최적해 아이디어의 핵심

• 첫번째로 어떤 동전을 선택하는지에 초점을 맞춤
• 예를 들어 coins={1, 3, 4}인경우 첫번째로 선택할 수 있는 동전의 값은 1, 3, 4중 하나입니다. 만약에 값이 1인 동전을 처음 선택한다면 남은 일은 최소한의 동전을 이용하여 합 9를 만드는 일이 됩니다.

 

점화식

• solve(x) = min(solve(x-1) + 1, solve(x-3) + 1, solve(x-4) + 1)
• x < 0 : INF
• x = 0 : 0

소스코드

public class Coin {
    private int[] coins;

    public Coin(int[] coins) {
        this.coins = coins;
    }

    public double solve(int x){
        if(x < 0){
            return Double.POSITIVE_INFINITY;
        }else if(x == 0){
            return 0;
        }
        double best = Double.POSITIVE_INFINITY;
        for(int coin : coins){
            best = Math.min(best, solve(x - coin) + 1);
        }
        return best;
    }
}

 

2.1. 메모이제이션(Memoization)

메모이제이션은 함수의 값을 계산한 뒤 이를 배열에 저장하는 방법입니다.

public class Coin {
    private int[] coins;
    private boolean ready[];
    private int[] dp;

    public Coin(int[] coins) {
        this.coins = coins;
        ready = new boolean[100];
        dp = new int[100];
    }

    public double solve(int x){
        if(x < 0){
            return Double.POSITIVE_INFINITY;
        }else if(x == 0){
            return 0;
        }else if(ready[x]){
            return dp[x];
        }
        double best = Double.POSITIVE_INFINITY;
        for(int coin : coins){
            best = Math.min(best, solve(x - coin) + 1);
        }
        ready[x] = true;
        dp[x] = (int) best;
        return best;
    }
}

 

2.2. 반복문을 이용한 구현

public class Coin {
    private int[] coins;

    public Coin(int[] coins) {
        this.coins = coins;
    }

    public double solve(int n){
        double[] dp = new double[n + 1];

        for(int x = 1; x <= n; x++){
            dp[x] = Double.POSITIVE_INFINITY;
            for(int coin : coins){
                if(x - coin >= 0){
                    dp[x] = Math.min(dp[x], dp[x - coin]+1);
                }
            }
        }
        return dp[n];
    }
}

 

2.3 해답 구성하기

최적해의 값뿐만 아니라 그 값이 어떻게 만들어지는지 구하는 경우가 있습니다. 새로운 배열을 정의하여 각각의 합을 만들기 위해 어떤 동전을 첫번째로 선택하는지를 지정하면 됩니다.

public class Coin {
    private int[] coins;

    public Coin(int[] coins) {
        this.coins = coins;
    }

    // 사용된 동전들의 배열을 반환
    public int[] solve(int n){
        double[] dp = new double[n + 1];
        int[] first = new int[n + 1];
        for(int x = 1; x <= n; x++){
            dp[x] = Double.POSITIVE_INFINITY;
            for(int coin : coins){
                if(x - coin >= 0 && dp[x - coin] + 1 < dp[x]){
                    dp[x] = dp[x - coin] + 1;
                    first[x] = coin;
                }
            }
        }
        return first;
    }
}

public class CoinTest {

    private Coin coin;

    @BeforeEach
    public void setup(){
        coin = new Coin(new int[]{1,3,4});
    }

    @Test
    public void testcase1(){
        int n = 10;
        List<Integer> list = new ArrayList<>();
        int[] actual = coin.solve(n);
        while(n > 0){
            list.add(actual[n]);
            n -= actual[n];
        }
        assertThat(list).isEqualTo(List.of(3,3,4));
    }

}

 

3. 해의 개수 세기

해의 개수 세기 문제는 동전 문제를 변형하여 합 x를 만드는 경우의 수를 세는 문제입니다. 예를 들어 coins = {1, 3, 4}, x=5이면 다음과 같이 6가지 방법이 존재합니다.

1 + 1 + 1 + 1 + 1
1 + 1 + 3
1 + 3 + 1
3 + 1 + 1
1 + 4
4 + 1

 

solve(x) : 합 x를 만드는 경우의 수

예를 들어 coins = {1, 3, 4}, x = 5라면 solve(5) = 6입니다.

 

점화식

• solve(x) = solve(x-1) + solve(x-3) + solve(x-4) (x > 0)
• x < 0 then 0
• x = 0 then 1
  • 합이 0을 만드는 경우는 동전을 사용하지 않는 수 1개뿐입니다.

x = 5이고 solve(x-1)의 의미는 합이 5원인 상태에서 1원 동전을 사용했을때 합이 4원을 만들 수 있는 경우의 수를 의미합니다. solve(5) = solve(4) + solve(2) + solve(1)의 의미는 다음과 같습니다.

• solve(5 - 1) : 합이 5원에서 1원을 사용하고 난후 합이 4원을 만들 수 있는 경우의 수
• solve(5 - 3) : 합이 5원에서 3원을 사용하고 난후 합이 2원을 만들 수 있는 경우의 수
• solve(5 - 4) : 합이 5원에서 4원을 사용하고 난후 합이 1원을 만들 수 있는 경우의 수
  • solve(1) = solve(1 - 1) : 합이 1원에서 1원을 사용하고 난후 0원을 만들 수 있는 경우의 수는 동전을 사용하지 않는 1개밖에 없습니다.

 

소스코드

// 해의 개수 세기
public class Coin {
    // count[x] : 합이 x가 되게 만들 수 있는 경우의 수
    public int solution(int n){
        int[] count = new int[n + 1];
        int[] coins = {1, 3, 4};
        count[0] = 1;
        for(int x = 1; x <= n; x++){
            for(int coin : coins){
                if(x - coin >= 0){
                    count[x] += count[x - coin];
                }
            }
        }
        return count[n];
    }
}

 

References

source code : https://github.com/yonghwankim-dev/algorithm_training/tree/main/src/main/java/kr/yh/chap06_dp/coin
알고리즘 트레이닝