알고리즘
[Java] 백준 16194번 카드 구매하기 2
J3SUNG
2023. 7. 22. 20:56
728x90
다이나믹 프로그래밍 문제입니다.
카드를 정확히 N개 구매할 때 최소비용을 구해야합니다.
1~N개 각각 살때의 비용에 대해서 주어집니다.
DP배열을 만들어서
1개로 살 수 있는 경우들을 입력해줍니다.
그리고 2개, 3개 ... n개 까지 모든 경우를 넣어줍니다.
for (int i = 1; i <= n; ++i) {
for (int j = 0; i + j <= n; ++j) {
calc[i + j] = Math.min(calc[j + i], calc[j] + arr[i]);
}
}
최종적으로 N개를 살 때 필요한 금액을 출력해주었습니다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n + 1];
int[] calc = new int[n + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; ++i) {
arr[i] = Integer.parseInt(st.nextToken());
calc[i] = 987654321;
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; i + j <= n; ++j) {
calc[i + j] = Math.min(calc[j + i], calc[j] + arr[i]);
}
}
bw.write(calc[n] + "\n");
bw.close();
}
}