[백준] 11052_카드 구매하기 (JAVA)

1. 문제

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

11052번: 카드 구매하기

---

 

 

2. 문제 풀이 겸 회고

1일 1 DP 중 ㅋㅋ 실력아 제발 늘어다오.. 이건 다시 풀어봐야겠닥.. 난이도 실바 1

 

풀이

5
5 10 9 8 7 6

이 뜻은 다 알겠지만 다시 해석해본다.

민규는 5장의 카드를 구하기 위해 최대의 비용을 알고 싶어 한다.

저 위의 배열 (5...  6)은 idx 위치만큼의 카드가 들어있는 카드팩의 비용이다.

즉, 배열의 idx는 카드팩 안에 idx 만큼의 카드가 들어가 있고 element는 그것의 비용이다.

1번 인덱스 ( 원래는 0번 인덱스지만 보기 편하기 1번이라고 하겠음)  즉 1장의 카드가 들어있는 카드팩의 비용은 5원이다. 이런 식으로 해석하면 된다.

 

여기서 중요한 것은 최대의 비용을 얻기 위한 것이다.

위의 예시는 5장의 카드를 원하는 것이니깐

우선 1장의 카드가 들어있는 팩을 5개 선택하면 5*5 = 25 임 

또한 만약 2장이 들어가 있는 카드팩과 1장이 들어가 있는 카드팩을 섞어서 선택하면 (2장의 카드팩 + 2장의 카드팩 + 1장의 카드팩) = 25의 경우도 나오고 3장이 들어가 있는 카드팩  + 2장이 들어가 있는 카드팩 경우도 있고.... 등등등

하지만 이렇게 하면 끝도 없다. 또한, 카드 범위가 최대 1000개임 그럼 이건 완탐으로 절대 불가능 ..!!!(시초) 

그래서 DP로 구현해야 한다!!!!

DP 배열을 구하자. (할 수 있다.. 우린...)

DP 에는 각 idx장의 카드팩이 만들 수 있는 최대의 비용을 쌓아주는 것이다. 

점화식을 세워야 한다.. (이게 제일 짜증)

*card 배열은 각각의 idx 장이 들어있는 카드팩의 가격 ( 입력으로 주어지는 것)

우선 1장이 들어가 있는 카드팩의 최대 비용은 자기 자신뿐이다. (dp[1]  = card[1]) 

여기서부턴 그냥 2장의 카드팩이라고 하겠음 

2장의 카드팩이 들어가 있는 최대 비용은  (dp[2] = dp[1] + dp[1]  or card[2]) -> 둘 중 큰 값을 저장하기 

이렇게 보면 이해 안 된다.  또 해보자.

3장의 카드팩이 들어가 있는 최대 비용은 (dp[3] = dp[1] + dp[2] or card[3])

dp에서 최대 비용을 저장하는 이유는 2장의 카드팩은 또 1장의 카드팩으로 세분화 되는데 굳이 그 작업은 안 해줘도 되니깐. 혹시 이해가 갔나..

안 갔으면 하나 더해보자

4장의 카드팩이 들어가 있는 최대 비용은 (dp[4] = dp[2] + dp[2] or dp[1] + dp[3]  or card[4])

이제 자세히 봐보자 4장이 선택될 수 있는 것 은 2장 2장, 1장 3장, 4장 이렇게이다.

3장 1장의 경우를 봐보자

3장은 또 1장 2장으로 쪼개지고 ... 하지만 최댓값을 저장해놓으면 굳이 다시 안 구하고 사용하면 됨

그래서이다. 이것도 이해 안 되면.. 댓글 달아주삼..

이렇게 해서 도출되는 식은  dp[i] = (dp[a] + dp[i-a]) or (card[i]) 

a는 유동적으로 변하는 값이고 i는 구하고자 하는 i장의 카드팩이다.

for (int i = 2; i <= N; i++) {
	for (int a = 1; a <= i / 2; a++) {
		if (max < dp[a] + dp[i - a]) {
			max = dp[a] + dp[i - a];
		}

	}
 }

i/2 해준 건 중복되는 거 피하기 위함이다. 

또한 max로 그 각각에 더한 값 나오는 거에서 최댓값 구해준 다음에 최종 보스인 자기가 원래 가지고 있던 값과 비교를 해줘서 더 큰 값을 최종적으로 dp[i]에 넣어주면 끗~~~~~~~~~~~~~~~~~~!

 

오늘은 말이 좀 길었다. 다음부턴 안 하겠다.

3. 코드

package net.acmicpc.solution;

import java.util.*;
import java.io.*;

public class Solution_11052_카드구매하기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine()); // 카드 개수
		StringTokenizer st = new StringTokenizer(br.readLine());

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

		for (int i = 1; i <= N; i++) {
			card[i] = Integer.parseInt(st.nextToken());
		}

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

		// 규칙: dp[i] = dp[a] + dp[i-a];
		dp[0] = 0;
		dp[1] = card[1];

		for (int i = 2; i <= N; i++) {
			int max = 0;
			for (int a = 1; a <= i / 2; a++) {
				if (max < dp[a] + dp[i - a]) {
					max = dp[a] + dp[i - a];
				}

			}
			if (card[i] < max) {
				dp[i] = max;
			} else {
				dp[i] = card[i];
			}

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

	}

}

 

 

피드백은 언제나 환영입니다 :) 🌳