[DP 연습] BOJ_11052 카드 구매하기 (S1)

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

11052번: 카드 구매하기

 

DP 점화식을 작성하는 부분 아이디어를 체크!

 

반복문을 두번 사용했는데, 왜 반복문을 두 번 사용했는지에 집중할 필요가 있을 것 같다.

반복문을 두번 사용한 이유를 찾기 위해서는 우선 문제의 요구사항을 파악하는 것이 필요할 것 같다.

 

문제의 요구사항이 무엇인가?

금액의 최댓값을 구하라는 것이였다.

금액의 최댓값을 구하기 위해서는,

배열에 저장된 값들의 최댓값을 구하기 이전에 최댓값을 저장해주는 과정이 필요하다.

그 부분을 구현해 주는게 cards 라는 배열의 i번째에 Math.max를 이용해서 최댓값을 저장해주는 부분이다.

 

그렇다면 어떤 값들을 비교해서 max 값을 결정하는가?

비교할 값들을 a,b로 나타내 주었다.

int a = cards[i]; // i
int b = cards[j] + cards[i-j]; // j + (i-j) = i

 

a가 의미하는게 뭔가?

카드를 i개 사기 위해서 필요한 비용을 의미한다.

정확하게 말하자면, 순수하게 i카드팩만 이용해서 i개를 갖기 위해 필요한 비용을 의미한다.

ex

1카드팩만 이용해서 카드 1개를 갖기 위해서는 1카드팩*1

3카드팩만 이용해서 카드 3개를 갖기 위해서는 3카드팩*1

 

b가 의미하는게 뭔가?

카드를 i개 사기 위해 필요한 비용을 의미한다.

정확하게 말하자면, 합이 i가 되는 카드팩들을 이용해서 i개를 갖기 위해 필요한 비용을 의미한다.

ex

카드 3개를 갖고 싶은 상황

a = 3카트팩만 이용하는 경우의 비용

b = 1카드팩과 2카드팩을 이용하는 경우의 비용

카드 10개를 갖고 싶은 상황

a = 10카드팩만 이용하는 경우의 비용

b = 1카드팩과 9카드팩을 이용하는 경우의 비용, 2카드팩과 8카드팩을 이용하는 경우의 비용...

 

b를 구하기 위해서는 변수가 두개 필요하게 된다.

i와 j를 두어서 이 둘의 합이 10인 경우를 찾게 된다면,

배열의 각 요소에 접근해서 값을 받아오고,

결국에는 b에 이 둘의 값의 합을 저장할 수 있다.

 

package algo0921;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 카드 구매하기
public class BOJ_11052 {
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		int N = Integer.parseInt(br.readLine());
		int[] cards = new int[N+1];

		// 입력
		st = new StringTokenizer(br.readLine(), " ");
		for (int n = 1; n <= N; n++) {
			cards[n] = Integer.parseInt(st.nextToken());
		}
		System.out.println(Arrays.toString(cards));
		
		
		// DP 점화식
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= i; j++) {
				int a = cards[i]; // i
				int b = cards[j] + cards[i-j]; // j + (i-j) = i
				cards[i] = Math.max(a, b);
				// 테스트 출력
				System.out.println("(i,j) = (" + i + "," + j + ")");
				System.out.println("(a,b) = (" + a + "," + b + ")");
				System.out.println("cards[" + i + "] = " + cards[i] + "\n");
			}
		}
		System.out.println(Arrays.toString(cards));
		
		// 출력
		Arrays.sort(cards);
		System.out.println(cards[N]);
	}
}