BOJ G5 2294 동전2 JAVA

2294번: 동전 2

---

문제 읽기

예전에 동전 1 문제를 풀었었는데 DP 문제를 잘 못하다 보니 그때도 고생했었다. 결국 풀지 못하고 블로그 찾아봤던 기억이..

이번에는 풀어보자! 하고 열심히 적으면서 했는데 예전 풀이가 기억나서 거기에 갇혀 좀 헤맸다. 기억이 아니라 논리에 의존해서 DP 문제를 풀고 싶구나.. 많이 풀다 보면 되겠지! 하는 생각이다.

---

문제 풀이

여러 차례 삽질했다. 바로 최종 문제 풀이로 넘어가도 상관 없을 듯 하다.

1차 삽질 : 2차원 배열. 동전의 종류 / 사용하는 동전의 개수

예전 동전1 문제를 풀었을 때 2차원 배열을 썼던 기억 때문에 당연히 2차원 배열이라 생각하고 접근했다. 동전의 종류마다 사용하는 동전 개수를 하나씩 증가 시키며 가치의 합을 표의 값으로 채워넣었다. 그래서 다음과 같이 나왔는데, 표에 최종적으로 뭘 저장해야 할 지도 모르겠고, 아무리 봐도 이건 아닌 거 같았다.

 

2차 삽질 : 2차원 배열. 동전의 종류 / 가치의 합

아차차 하고 표의 열에 들어가는 값을 바꿨다. 보통 냅색 문제가 N, W를 각각 행렬로 보는 것도 잇따라 기억났다. 바꾸니까 뭔가 되는 거 같았고, 점화식까지 세웠다.

그런데 넣으니까 계속 3퍼센트에서 틀렸다고 나왔다. 뭐가 문제지 하고 문제를 계속 읽어보고 입력값의 중복도 제거해보고 답이 없으면 -1로 출력하고 여러가지 했는데 변화가 없었다(꺾임)

3차.. 블로그 서칭.. 최종 풀이

[알고리즘] - 백준 2294번 : 동전2 (JAVA)

결국 블로그 찾아봤다. 다른 점은 다음과 같다.

• 1차원 DP 배열을 쓴다
  • 1~K까지의 가치의 합 배열
• 이전 값을 갱신하여 같은 곳에 채운다
• DP 배열의 초기화
  • 0번째 위치를 제외하고는 큰 값으로 채워준다.
• 점화식
  • DP[k] = Math.min(DP[k], DP[k-coins[n]] + 1)
  사용하는 동전의 종류를 하나씩 증가 시키면서,새로운 동전도 함께 사용했을 때 k라는 값을 만들 수 있는 동전의 개수를 비교해서 ⇒ DP[k-coins[n]] + 1
• 최솟값을 저장한다
• 현재까지 동전을 사용했을 때 k라는 값을 만들 수 있는 동전의 개수와, ⇒ DP[k]

---

코드

package ps.ㄱSolving;

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

public class BOJ_G5_2294_동전2 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] coins = new int[N];
        for (int i = 0; i < N; i++){
            coins[i] = Integer.parseInt(in.readLine());
        }

        //dp logic
        int[] dp = new int[K+1];
        for (int j = 1; j < K+1; j++){
            dp[j] = 1000000;
        }
        for (int n = 1; n < N+1; n++){
            for (int k = coins[n-1]; k < K+1; k++){
                dp[k] = Math.min(dp[k-coins[n-1]] + 1, dp[k]);
            }
        }

//        System.out.println(Arrays.toString(dp));
        System.out.println((dp[K] == 1000000)? -1 : dp[K]);
    }
}

 

살짝 한 풀이처럼 되어버렸지만.. DP 잘 푸는 날까지 화이팅..!!