[백준/JAVA] 2294번: 동전 2

🔺 문제

2294번: 동전 2

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    public final static int MAX  = 100001;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int dp[] = new int[k + 1];    // dp[i] : 값 i를 만들기 위한 최소 동전 개수
        Arrays.fill(dp, MAX);
        dp[0] = 0; // 처음은 0!!
 
        int coin[] = new int[n + 1];  // 동전 배열        
        for(int i = 1 ; i <= n ; i++) {
            coin[i] = Integer.parseInt(br.readLine());
            
            for(int j = coin[i] ; j <= k ; j++) {
                dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1);
            }
        }
 
        System.out.println(dp[k] == MAX ? -1 : dp[k]);
        br.close();
    }
}

✅ 해결 아이디어
✔ DP
- dp[ i ] : 값 i를 만들기 위한 최소 동전 개수

 

💥 유의사항

• dp[0]의 값은 0이어야 함.

 

 

---

🔺 다른 풀이들

- 과정 (복습용)             

백준 2294번 동전 2(JAVA)

[Java] [백준 2294][DP] 동전 2

 

 

---

💬 느낀 점

앗... 약간 감이 잡힐랑말랑...

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

[Java] 백준 2294 : 동전 2