[백준/JAVA] 2293번: 동전 1

🔺 문제

2293번: 동전 1

본인 아님

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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 = Integer.parseInt(st.nextToken());   // 동전 종류
        int k = Integer.parseInt(st.nextToken());   // 목표가
        
        int[] coin = new int[n + 1];   // 동전 배열
        int[] DP   = new int[k + 1];   // DP[i] = j : i원 만드는 경우의 수 j
        DP[0] = 1;
        
        for(int i = 1 ; i <= n ; i++) {
            coin[i] = Integer.parseInt(br.readLine());
            
            for(int j = coin[i] ; j <= k ; j++) {
                DP[j] += DP[j - coin[i]];
            }
        }
        System.out.println(DP[k]);
        br.close();
    }
}

✅ 해결 아이디어
✔ DP
- DP[ i ] = j  ⇒ j는 i원 만드는 데 가능한 경우의 수

 

 

---

🔺 다른 풀이들

- 감격적인 과정 설명... (동전 가지 수 늘려가면서 메모이제이션... 기억... 복습용)

[백준 2293번] 동전 1 (java)

[백준] 2293번 : 동전 1 – JAVA [자바]

 

 

- 점화식 세우는 과정 !!!!

백준 2293 동전 1 JAVA

---

💬 느낀 점

아직도 점화식을 못 세우는 사람이 있다?!

혼자서도 잘 풀고 싶,,,

 

 

1회독	2회독	3회독	4회독	5회독
V	7/12

---

(참고)

[백준 2293 : JAVA] 동전1 / Dynamic Programming