[백준] 11052 - 카드 구매하기 (Java)

[백준] 11052 - 카드 구매하기 (Java)

문제

https://www.acmicpc.net/problem/11052

풀이/후기

카드 N개를 구매하려고 할 때,

1개의 카드팩 구입 후 N-1개 카드 구입

2개의 카드팩 구입 후 N-2개 카드 구입

...

i개의 카드팩 구입 후 N-i개 카드 구입

N개의 카드팩 구입 후 0개 카드 구입

 

dp배열에는 카드 구매 시 최대 가격이 담겨진다.

N개를 구매하고자 할 때 기본적으로 N개의 카드팩이 주어지니까

구입하고자 하는 카드의 개수(N)와 동일한 카드팩(N) 한개만 사는 경우가 존재한다.

즉, dp[N]의 기본값은 P[N]이다.

 

여기서 다른 개수의 카드팩을 조합하여 N개를 구매하는 경우를 고려한다.

위에서 생각한 것처럼 i개의 카드팩을 구매 후 N-i개를 추가적으로 구입하면 된다.

dp[N-i] 배열에는 이미 N-i개를 구매할 때의 최대 가격이 들어있으니

dp[N] = P[i] + dp[N-i]의 식을 얻을 수 있다.

 

그래서 P[N]과 P[i] + dp[N-i] 두 개의 값 중 더 큰 값을 dp에 저장하면 점화식은 아래와 같다.

dp[N] = Math.max(P[N], P[i] + dp[N-i]);

코드

package DynamicProgramming;

import java.io.*;

public class Problem11052 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		String[] in = br.readLine().split(" ");
		int[] P = new int[N + 1];

		for (int i = 1; i < N + 1; i++) {
			P[i] = Integer.parseInt(in[i - 1]);
		}

		int[] dp = new int[N + 1];

		for (int x = 1; x < N + 1; x++) {
			dp[x] = P[x];
			for (int y = 1; y < x; y++) {
				dp[x] = Math.max(dp[x], P[y] + dp[x - y]);
			}
		}

		System.out.println(dp[N]);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/4f4ded407050348c7a697f8856c505c7ab9b2432

참고

https://developer-mac.tistory.com/69