백준 2294 자바 - 동전 2 (BOJ 2294 JAVA)

문제 : boj2294

 

 

1.

  우선 문제에서 필요없는 정보를 제한해보자.

 

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

-> 이 조건은 해당 가치를 표현하는 경우의 수를 구할때나 의미가 있다. '사용한 동전의 최소 개수'를 구하는 문제이므로 무시해도 된다.

 

1.2 '가치가 같은 동전이 여러 번 주어질 수도 있다.'

-> 가치가 동일한 동전의 경우 연산을 느리게 할 뿐이므로, 동일한 동전이 주어진 경우는 HashSet 등을 사용해 제거하면 될 것임을 생각할 수 있다.

 

1.3 'k <= 10000인데, 동전의 가치는 최대 100000'

-> k값을 초과하는 가치를 가지는 동전은 제거하고 생각해도 동일하다.

 

 

2.

  동전의 가치를 간선의 거리로 생각해보면 bfs나 dijkstra로도 가능할 것 같다. 하지만 dp가 먼저 생각났기에 dp로 풀어봤다.

 

dp[x] 을 가치 x를 표현하기 위해 필요한 동전의 최소 개수라 하자.

그럼 x를 1부터 k까지 증가시키면서 모든 동전의 가치에 대해

 

dp[x] = min( dp[x - n개의 각 코인의 가치] + 1 )

 

가 된다. 입력이

 

3 5

1

2

3

 

이라 한다면 다음과 같이 나타낼 수 있다.

 

2.1 x가 1일 때는 동전1을 사용해서 dp[1-1]+1 이 최소값이다. (동전2와 동전3은 dp[-1]과 dp[-2]이므로 불가)

 

2.2 x가 2일땐 dp[2-1]+1과 dp[2-2]+1 중 작은 값을 고르면 된다. 1이 된다. 즉, 동전2짜리 하나만 쓴 경우이다.

 

2.3 x가 3일땐 dp[3-1]+1, dp[3-2]+1, dp[3-3]+1 중 작은 값을 고르면 된다. 동전3짜리 하나만 쓴 경우인 1이 된다.

 

2.4 x가 4일때도 마찬가지이다. 동전1과 3을 쓴 경우, 2와 2, 3과 1을 쓴 경우 중 어느것을 택해도 되므로 2가 된다.

 

2.5 x가 5일땐 4의 가치를 표현한 경우 이외에 가치2와 가치3을 표현한경우에 각각 동전3과 동전2를 추가로 사용하면 된다. 최종적으로 2가 답이다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    private static final int INF = 10001;
    
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        ArrayList<Integer> coins = new ArrayList<>();
        HashSet<Integer> dupCoinChk = new HashSet<>();
        while(n-->0) {
            int cur = Integer.parseInt(br.readLine());
            if (dupCoinChk.contains(cur) || cur > k) continue;

            dupCoinChk.add(cur);
            coins.add(cur);
        }

        int[] dp = new int[k+1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int i = 1; i <= k; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i-coins.get(j) < 0) continue;
                if (dp[i] > dp[i-coins.get(j)]+1)
                    dp[i] = dp[i-coins.get(j)]+1;
            }
        }

        System.out.println(dp[k]==INF?-1:dp[k]);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}