<Algorithm> 211. 동전(BOJ)
by BFine반응형
9084번 동전(BOJ)
사용 알고리즘 : DP
- 몇번 풀어봤던 문제인데 한번에 떠오르질 않았다. 이번에 풀면서 확실하게 정리해둬야 겠다.
- 이전에 풀었던 문제들이 가로로 직선적인 흐름이라면 이 문제는 세로로 직선적인 흐름을 가지는 것 같다.
- 차곡차곡 쌓는게 아니라 한번 쭉 쌓고 다시와서 덧붙여 쌓는 방식의 문제이다.
문제에 대한 접근&생각
- 동전 최대 20개, 최대 금액 10000 -> 너무 많은 경우의 수 -> 완전탐색 X , DP!
- 이전에 만든 금액을 통해 만들려는 금액의 동전 개수를 알 수 있음 -> 메모제이션!
코드
|
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
27
28
29
|
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
/***************************
* DP를 이용하여 이전의 결과에
* 현재 결과를 누적한다.
***************************/
while(T-->0) {
int n = sc.nextInt();
int[] coin = new int[n];
for(int i = 0; i < n; i++)
coin[i] = sc.nextInt();
int m = sc.nextInt();
int[] dp = new int[m+1];
dp[0] = 1;
for(int i = 0; i < n; i++)
for(int j = coin[i]; j <= m; j++)
dp[j] += dp[j - coin[i]];
System.out.println(dp[m]);
}
}
}
|
|
|
|
|
|
|
cs |
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
| <Algorithm> 213. 조짜기(BOJ) (0) | 2019.06.01 |
|---|---|
| <Algorithm> 212. 제곱수의 합(BOJ) (0) | 2019.05.31 |
| <Algorithm> 210. 줄세우기(BOJ) (0) | 2019.05.31 |
| <Algorithm> 209. 파일합치기(BOJ) (0) | 2019.05.30 |
| <Algorithm> 208. 만취한 상범(BOJ) (0) | 2019.05.28 |
블로그의 정보
57개월 BackEnd
BFine