[BOJ 2294] 동전 2 - JAVA, Gold5

https://www.acmicpc.net/problem/2294

2294번: 동전 2

사용한 알고리즘 : DP

 

풀이전략

1. 우선순위 큐를 이용한 다익스트라 알고리즘으로 풀이 (실패, 메모리초과)

처음엔 우선순위 큐를 이용한 다익스트라 알고리즘을 사용하여 문제를 풀이했다.

그런데 메모리 초과 문제가 발생했다.

 

문제에서 주어진 메모리 제한은 128MB인데, 

내가 선언한 클래스를 원소로 가지는 우선순위 큐는 노드 하나 당 8 byte를 차지했다.

 

그런데 우선순위 큐를 이용한 다익스트라 알고리즘은 시간 복잡도가 O(NlogN)로

한 번의 연산에서 하나의 노드를 생성하고 우선순위 큐에 삽입했었다.

 

그런데 k의 크기는 1~10000으로 최악의 경우

10000 * log10000 = 10000 * 9.965784 = 99657.84번 수행하며, 해당 수만큼 노드를 생성한다.

즉, 최악의 경우 차지하는 메모리는 99657.84 * 8 = 79,726.272 byte = 778.576875 MB로

메모리 초과가 발생한다.

 

1. DP를 사용한 풀이(성공)

문제 풀이를 DP 방식으로 변환했고 점화식은 아래와 같다.

Arrays.fill(d,INF);

d[0]=0;
for(int i=1;i<=k;++i){
    for(int x:coins){
        if(i>=x) d[i]=Math.min(d[i],d[i-x]+1);
    }
}

d[i]는 i원을 만드는데 최소한으로 사용되는 동전의 개수를 저장한다.

 

처음 배열 변수 d 내부의 모든 값을 무한으로 통일시키고 d[0]만 0으로 정의한다.

그래야만 d[i]에 값 비교를 했을 때 더 작은 값으로 교체해줄 수 있기 때문이다.

 

coins는 입력받은 동전의 가치를 저장한 배열로,

1, 5, 12원의 동전을 입력받은 경우

i가 특정 동전의 가치보다 크거나 같은 모든 경우에,

동전의 가치만큼 이전의 d[i-(동전의가치)]+1과현재 d[i]를 비교하여 더 작은 값을 d[i]에 저장한다.

 

위와 같은 과정을 반복하면 최종적으로 d[k]에 우리가 도출해내려고 했었던

k원을 만드는데 쓰인 최소의 동전 개수가 저장된다.

제출코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
    static int INF=(int)1e9;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int coins[] = new int[n];

        int d[] = new int[k+1];
        for (int i = 0; i < n; ++i) {
            coins[i] = Integer.parseInt(br.readLine());
        }

        Arrays.fill(d,INF);

        d[0]=0;
        for(int i=1;i<=k;++i){
            for(int x:coins){
                if(i>=x) d[i]=Math.min(d[i],d[i-x]+1);
            }
        }

        if(d[k]!=INF) bw.write(d[k]+"\n");
        else bw.write(-1+"\n");
        bw.flush();
        bw.close();
    }
}