#2294 동전2
난이도 : 실버 1
유형 : DP
▸ 문제
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
▸ 입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
▸ 출력
첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.
문제 풀이
동전1 문제의 상향 버전이다. 주어진 동전의 종류로 k원을 만들 수 있는 동전의 최소 개수를 구하는 문제이다. Bottom-up방식으로 주어진 n개의 동전을 차례대로 탐색하여 만들 수 있는 개수의 최솟값을 구하는 식으로 접근하였다.
구상
dp는 2차원 배열로, 주어진 동전(coin[i])의 금액과 j원을 만들 수 있는 동전의 개수를 저장한다.
- dp[i][j] = coin[0~i]들로 j원을 만들 수 있는 동전의 최소 개수
- 동전 가치의 최대는 100,000이므로 최솟값 비교를 위해 dp배열을 100,001로 초기화해준다
시뮬레이션
- 주어진 코인 n개를 순차적으로 탐색해준다. i : 0~n-1
- 현재의 동전(coin[i])가 j보다 작거나 같으면 해당 동전으로 j원을 만들 수 있는 최소의 동전 개수를 구해준다. j : 1~k
idx | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
coin[0]=1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
coin[1]=5 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 6 | 3 |
coin[2]=12 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 | 1 | 2 | 3 | 3 |
해당 2차원 배열 dp 탐색과정을 코드로 표현하면 다음과 같다.
for(int i=0; i<n; i++) {
int now = coin[i];
for(int j=1; j<k+1; j++) {
if(i==0) {
if(j>=now) dp[i][j] = Math.min(dp[i][j-now]+1, dp[i][j]);
}else {
if(j>=now) {
dp[i][j] = Math.min(dp[i][j-now]+1,dp[i-1][j]);
}else {
dp[i][j] = dp[i-1][j];
}
}
}
}
최적화
위의 시뮬레이션을 보면 알겠지만 사실상 dp의 값이 변경되는 부분은 j= coin[i]일 때 부터이다. 필요없는 연산과정을 제거하고 이를 단축시키면 dp배열과 코드를 다음과 같이 줄일 수 있다.
dp는 1차원 배열로 주어진 동전(coin[i])의 금액과 j원을 만들 수 있는 동전의 개수를 저장한다.
- dp[i] = coin[0~i]들로 j원을 만들 수 있는 동전의 최소 개수
for(int i=0; i<n; i++) {
for(int j= coin[i]; j< k+1; j++) {
dp[j] = Math.min(dp[j], dp[j - coin[i]] +1);
}
}
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
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];
for(int i=0; i<n; i++) {
coin[i] = Integer.parseInt(br.readLine());
}
int[] dp = new int[k+1];
Arrays.fill(dp, 100001);
dp[0] = 0;
for(int i=0; i<n; i++) {
for(int j= coin[i]; j< k+1; j++) {
dp[j] = Math.min(dp[j], dp[j - coin[i]] +1);
}
}
System.out.println(dp[k] == 100_001? -1 : dp[k]);
}
}
'Dot Algo∙ DS > PS' 카테고리의 다른 글
[BOJ] 백준 1600번 말이 되고픈 원숭이 (Java) (0) | 2021.08.10 |
---|---|
[BOJ] 백준 7576번 토마토 (Java) (0) | 2021.08.09 |
[BOJ] 백준 2293번 동전1 (Java) (0) | 2021.08.07 |
[BOJ] 백준 1520번 내리막 길 (Java) (0) | 2021.08.06 |
[BOJ] 백준 12865번 평범한 배낭 (Java) (0) | 2021.08.05 |