백준알고리즘 2293번 동전 1

문제 링크

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

동전의 합이 3이고 1원 2원이 주어졌다면 

{1,1,1}, { {2,1} 또는 {1,2} } 2가지의 답이 나와야 하지만 아래의 소스는 3가지가 나온다. 모든 경우의 수를 출력하기 때문에 답이 아니다.

package com.ktko.Success;

import java.util.Scanner;

///첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.
//https://www.acmicpc.net/problem/2293

public class Coin1 {
    static int[] result;
    static int[] coin;
    static int n, k;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = Integer.parseInt(scan.nextLine().trim());

        result = new int[11];
        coin = new int[n];
        for (int i = 0; i < result.length; i++)
            result[i] = -1;
        for (int i = 0; i < coin.length; i++) {
            coin[i] = Integer.parseInt(scan.nextLine().trim());
        }

        System.out.println(coinDP(k));
    }

    static public int coinDP(int value) {
        if (value < 0)
            return 0;

        if (value == 0) {
            return 1;
        }

        if (result[value] != -1)
            return result[value];
        result[value] = 0;
        for (int i = 0; i < coin.length; i++) {
            if (value >= coin[i]) {
                result[value] = result[value] + coinDP(value - coin[i]);
            }
        }

        return result[value];
    }
}

아래의 예제는 중복되는 코인을 제외하고 정답을 출력한다.

package com.ktko.Success;
import java.util.Scanner;

///첫째줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다.
//https://www.acmicpc.net/problem/2293

public class Coin1 {
    static int[] result;
    static int[] coin;
    static int n, k;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        k = Integer.parseInt(scan.nextLine().trim());

        result = new int[k + 1];
        coin = new int[n];

        for (int i = 0; i < coin.length; i++) {
            coin[i] = Integer.parseInt(scan.nextLine().trim());
        }
        coinDP();
        System.out.println(result[k]);
    }

    static public void coinDP() {
        result[0] = 1;
        for (int j = 0; j < coin.length; j++) {
            for (int i = 1; i < k + 1; i++) {
                if (coin[j] <= i)
                    result[i] = result[i] + result[i - coin[j]];
            }
        }
    }
}

다이나믹 프로그래밍은.. 점화식을 찾는게 가장 중요한데 정말 어려운 것같다.. 풀어도 풀어도 익숙지 않아서 힘들다.

푼 것을 또 풀어보고 반복해서 익숙해지자.