[Algorithm] 백준 DP문제 - 동전 2(2294) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 DP문제 - 동전 2 자바 풀이를 진행하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/2294

2294번: 동전 2

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int k = parseInt(st.nextToken());
        Coin coin = new Coin(n, k);
        
        for (int i = 0; i < n; i++) {
            coin.setCoin(parseInt(br.readLine()));
        }
        
        coin.run();
        System.out.println(coin.getResult());
    }
}

class Coin {
    int n;
    int k;
    int[] dp; // 각 인덱스에 들어갈 값은 코인의 최소 개수
    int result; // 결과 저장 
    List<Integer> coins = new ArrayList<>(); // 코인 값 저장 
    
    Coin (int n, int k) {
        this.n = n;
        this.k = k;
        dp = new int[k + 1]; 
        Arrays.fill(dp, Integer.MAX_VALUE); // 모두 최고값으로 초기화
    }
    
    void setCoin(int won) {
        coins.add(won);
    }
    
    void run() {
        
        dp[0] = 0; // 0을 만드는 경우는 0개임
        for (int i = 1; i <= k; i++) {
            for (Integer coin : coins) {
                if (i - coin < 0 || dp[i - coin] == Integer.MAX_VALUE) continue; // 만약 인덱스가 0 미만이거나, 만들 수 없는 값인 경우
                dp[i] = Math.min(dp[i - coin] + 1, dp[i]); // 코인의 값을 인덱스로 뺀다면 그 값이 설정   
            }
        }
        
        if (dp[k] == Integer.MAX_VALUE) result = -1;
        else result = dp[k];
    }
    
    int getResult() {
        return result;
    }
    
}

 

2. 풀이 중점 사항

 

Memozation을 사용할 DP를 금액으로 설정하고 문제를 해결하였습니다.

각 동전은 coin이라는 리스트에 저장한 후,

1 ~ k까지 (각 경계 포함) for문을 돌리되, 각 코인을 내부에서 순환합니다. (빅오 n^2)

 

dp[i] = Math.min(dp[i - coin] + 1, dp[i]); // 코인의 값을 인덱스로 뺀다면 그 값이 설정

dp[i - coin]은 dp는 금액을 메모한 배열이므로 i - coin은 i - coin 금액에 있는 동전 최소 개수가 됩니다.

즉, 동전이 500이고, 현재 i = 700일 때, dp[200]에서 500원 동전 한 개만 더해주면 700을 만들 수 있는 원리입니다.

따라서 다음의 점화식을 작성하여 문제를 해결할 수 있었습니다.

 

이상으로 DP 동전 2 문제 풀이를 마치도록 하겠습니다. 감사합니다.!!