[백준] code.plus(다이나믹 프로그래밍,JAVA)2294번, 동전 2

문제 링크

2294번: 동전 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

이 문제에 핵심은

 

1. n가지 종류의 동전이 존재하며 중복된 가치를 가질 수 있습니다.

2. n개의 동전을 적절히 사용하여 k를 만드는데 동전을 사용하는 최소 횟수를 결과로 출력합니다.

3. 동일한 동전을 반복하여 사용이 가능합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 동전에 대한 정보를 저장합니다.

 

2. BFS와 DP를 이용해서 n개의 동전을 이용해서 k에 도달할 때 최소 동전 사용 횟수를 구합니다.

 

3. DP[k]의 값을 결과로 출력합니다.

 

 

DP[i]의 형태

 

숫자 i을 만드는데 동전을 사용하는 최소 횟수를 저장합니다.

 

 

중복되는 가치를 가진 코인에 대하여.

 

똑같은 가치의 코인들을 던지더라도 도달하는 값은 동일하기 때문에

boolean[] coinCheck의 배열을 이용해서 중복되는 가치가 존재하면 해당 동전은 저장하지 않았습니다.

 

 

예제입력 1.

 

1. 입력되는 동전에 대한 정보를 저장합니다.

 

n = 3

k = 15

 

coin1: 1

coin2 : 5

coin3 : 12

 

2.  BFS와 DP를 이용해서 n개의 동전을 이용해서 k에 도달할 때 최소 동전 사용 횟수를 구합니다.

 

던진 횟수 : 1

 

1 : coin1

5 : coin2

12 : coin3

 

던진 횟수 : 2

 

2 : coin1 + coin1

6 : coin1 + coin2

13 : coin1 + coin3

10 : coin2 + coin2

 

던진 횟수 : 3

 

3 : coin1 + coin1 + coin1

7 : coin1 + coin1 + coin2

14 : coin1 + coin1 + coin3

11 : coin1 + coin2 + coin2

15 : coin2 + coin2 + coin2

 

3. DP[k]의 값을 결과로 출력합니다.

 

DP[k] = 15

 

DP[k]를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 n,k에 대한 정보를 나누었습니다.
• coinCheck 배열을 이용해서 중복되는 가치의 코인은 저장하지 않았습니다.
• cal함수를 실행하여의 DP[]값들을 저장합니다.
• DP[k] 값을 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal는 BFS + DP를 이용해서 도달할 수 있는 숫자들의 최소 동전 횟수들을 DP[]에 저장합니다.

 

import java.util.*;
import java.io.*;
public class Main {
    static int N,K;
    //동전에 대한 가치 저장하는 리스트
    static ArrayList<Integer> coins = new ArrayList<>();
    //중복된 가치를 가진 동전 방지를 위한 확인 배열
    static boolean[] coinCheck = new boolean[10001];
    static int[] DP;	//k을 만드는데 사용하는 최소 동전 횟수를 저장하는 메모이제이션
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        DP = new int[K+1];
        //입력되는 동전 정보 저장
        for(int i=0;i<N;i++){
            int temp = Integer.parseInt(br.readLine());
            if(temp <= K && !coinCheck[temp]){
                coins.add(temp);
                coinCheck[temp] = true;
            }
        }
        //DP값 초기화
        Arrays.fill(DP, 10001);
        DP[0] = 0;
        cal();	//최소 동전 횟수 DP[]에 저장하는 함수 실행
        if(DP[K] == 10001)	//k를 도달하지 못할 때
            bw.write("-1");
        else		//k도달 시 최소 동전 횟수 BufferedWriter 저장
            bw.write(DP[K] + "");
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //최소 동전 횟수를 DP[]에 저장하는 함수
    static void cal(){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        while(!queue.isEmpty()){
            int cur  = queue.poll();
            if(cur==K)	//k도달 시
                return;
            //코인들을 사용하면서 값들을 탐색
            for(int i=0;i<coins.size();i++){
                if(cur + coins.get(i) <= K && DP[cur + coins.get(i)] > DP[cur] + 1){
                    DP[cur + coins.get(i)] = DP[cur] + 1;
                    queue.add(cur + coins.get(i));
                }
            }
        }
    }
}