[PS] 백준2294 : 동전 2(Java)

문제

2294번: 동전 2

2294번: 동전 2

 

---

풀이

다이나믹 프로그래밍으로 분류된 문제로 간단한 메모이제이션을 통해 풀이가 가능.

접근법

• 입력으로 주어진 동전으로 목표가치 K를 만드는 최소 개수를 구하는 문제로 DP문제인 만큼 Sub Problem을 찾으려 했음.
  • Sub Problem : 각각의 동전으로 1원부터 목표(K)까지의 가치를 만들기위한 사용한 동전의 최소개수
• 부분 문제를 찾았으니 먼저 해야할 것은 부분 해를 저장할 dp배열을 선언하는 것.
  • 최소개수를 찾는 문제로 dp[0]를 제외한 나머지 값은 INF로 초기화 (최소값을 찾는 여정이기때문에 최대값으로)

초기화한 dp배열

• 예제입력에 대해서 설명해보자면
• 목표가치(K)인 15원을 만들기 위해 각각의 동전에 대해 1원부터 1~15원까지 만들기위한 개수를 찾아 메모이제이션을 수행.

Case 1. coin == 1

1원 동전에 대한 부분 해

Case 2. coin == 3

• 3원의 경우 목표가치가 3일 때 1개로 만들 수 있기 때문에 최소개수 갱신
  • 특정 목표가치(3)에서 어떻게 최소값을 비교하는지에 대한 구문이해가 중요!
  • dp[3] : 앞선 1원 동전의 비교에서 3개로 만들 수 있었기에 3.
  • dp[3-3]+1 : 목표가치 3에서 현재동전 3을 뺐을 때의 기존 값(dp[0])에서 +1을 함으로써 현재 동전을 추가했을 때의 개수를 알 수 있음.
• 12원 동전의 경우에는 3원 동전과 마찬가지로 특정 목표가치가 12일 때 dp[0]+1이 최소가 되기에 dp[12]에서 최소개수가 1로 갱신됨.

목표가치 K를 만들기 위한 최소 동전개수를 알기 위해 1원부터 K까지 각각의 동전을 통해 만들 수 있는 최소개수(Sub Problem)를 메모이제이션 하며 최종적으로 알 수 있게됨.

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

//BOJ_2294 동전 2
public class Main {
    static int N, K;
    static int INF = 1000000000;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); //동전 종류
        K = Integer.parseInt(st.nextToken()); //가치의 합

        arr = new int[N];
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int[] dp = new int[K+1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for(int i=0; i<N; i++) {
            //각각의 동전의 경우에
            int coin = arr[i];
            for(int j=1;j<=K; j++) {
                if(j >= coin) { //동전의 가치보다 j가 클 경우
                    dp[j] = Math.min(dp[j], dp[j-coin]+1); //dp[j]는 현재 값과 현재 동전의 가치를 뺀 부분 해 둘 중 최소값으로 갱신
                }
            }
        }

        if(dp[K] >= INF) System.out.println(-1); //만들 수 없는 경우
        else System.out.println(dp[K]);

    }
}

---

반례

Input
2 10
2
3

Answer
4

---

정리

-1 예외처리 안해서 한번 틀려버림..

• DP를 풀 때 중요한 건 해당 문제를 풀기 위해 어떤 것을 메모이제이션 하느냐.
  • 즉 부분 문제(Sub Problem)을 찾는 것이라 생각함..
• 하지만 부분 문제를 찾는 것도 되게 힘든 일이기 때문에 DP를 시작한지 얼마 되지 않았다면 머리부터 박지 말고 최소한의 사고를 한 후 접근법을 참조하여 다양한 유형에 대한 풀이법을 암기하는 식으로 다가가는게 스트레스를 덜 받을 것 같음..

즉. DP는 점화식 세우는데 타고난게 아니라면 암기싸움이라 생각함!!