https://www.acmicpc.net/problem/11052
11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
풀이 방법
다이나믹 프로그래밍을 사용하여 풀었다.
dp 문제를 풀 땐 먼저 구하고자 하는 것이 무엇인지를 생각하는 것이 가장 쉬운 접근 방법인 것 같다.
구하고자 하는 것이 N개 카드 구매 시 지불할 금액의 최댓값이 이므로 DP 배열의 값을 각 구매 개수에 따른 지불 최댓값을 저장해야겠다고 생각했다. 즉, 카드 2개 구매 시 최댓값이 10이면 dp[2] = 10이 되는 것이다.
카드 구매 시 i번 카드팩을 포함하는 경우와 포함하지 않는 경우 두 가지로 나누어 최댓값을 비교해주면
점화식은 총 j개의 카드를 구매한 경우 dp[j] = max(dp[j-i] + p[i], dp[j])가 된다. (단, i <= j <= N)
따라서, 1~N의 모든 카드팩에 대해 i번 카드팩을 구매했을 때 가능한 모든 구매 개수에 대해 dp 점화식을 사용하여 dp 값을 갱신해주면 된다.
코드
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] dp = new int[N+1];
int[] P = new int[N+1];
// 카드팩 입력
String[] line = br.readLine().split(" ");
for(int i=1; i<=N; i++) {
P[i] = Integer.parseInt(line[i-1]);
}
for(int i=1; i<=N; i++) {
for(int j=i; j<=N; j++) {
dp[j] = Math.max(dp[j-i] + P[i], dp[j]);
}
}
System.out.println(dp[N]);
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 13975 파일 합치기 3 자바(java) (0) | 2024.02.07 |
|---|---|
| 백준 27447 주문은 토기입니까? 자바(java) (0) | 2024.02.01 |
| 백준 17609 회문 자바(java) (2) | 2024.01.31 |
| 백준 21315 카드 섞기 자바(java) (2) | 2024.01.30 |
| 백준 16166 서울의 지하철 자바(java) (0) | 2024.01.30 |