반응형
🔺 문제
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
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();
}
}
|
cs |
✅ 해결 아이디어
✔ DP
-DP[ i ] = j
⇒ j는 i원 만드는 데 가능한 경우의 수
🔺 다른 풀이들
- 감격적인 과정 설명... (동전 가지 수 늘려가면서 메모이제이션... 기억... 복습용)
- 점화식 세우는 과정 !!!!
💬 느낀 점
아직도 점화식을 못 세우는 사람이 있다?!
혼자서도 잘 풀고 싶,,,
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 7/12 |
(참고)
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 2667번: 단지번호붙이기 (0) | 2023.05.24 |
---|---|
[백준/JAVA] 2294번: 동전 2 (0) | 2023.05.23 |
[백준/JAVA] 3085번: 사탕 게임 (0) | 2023.05.23 |
[백준/JAVA] 16916번: 부분 문자열 (0) | 2023.05.22 |
[백준/JAVA] 1806번: 부분합 (0) | 2023.05.22 |