[Java] BOJ 11052번 카드 구매하기

11052번: 카드 구매하기

---

풀이

DP를 사용하여 해결했습니다.

 

만약 N = 4일 경우는 4장을 뽑았을 때 최대 값이므로

① 1장을 이미 뽑았을때의 최대값 + P[3] (3장이 있는 카드팩의 비용)

② 2장을 이미 뽑았을때의 최대값 + P[2] (2장이 있는 카드팩의 비용)

③ 3장을 이미 뽑았을때의 최대값 + P[1] (1장이 있는 카드팩의 비용)

④ P[4] (4장이 있는 카드팩의 비용)

중 최대인 값을 선택하면 4장을 뽑았을때의 최대값을 만들 수 있습니다.

---

코드

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

public class Main {
	public static int N;
	public static int[] P = new int[1001];
	public static int[] memo = new int[1001];
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(br.readLine());
		
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 1; i <= N; ++i) {
			P[i] = Integer.parseInt(st.nextToken());
		}
		
		for (int i = 1; i <= N; ++i) {
			// 4장을 뽑는다면 1-3, 2-2, 3-1, 4-0의 방법이 존재한다!
			for (int j = 1; j <= i; ++j) {
				// 각 방법들 중 최대값을 찾는다
				memo[i] = Math.max(memo[i], memo[i - j] + P[j]);
			}
		}
		
		System.out.println(memo[N]);
	}
}

---

pyo7410/Algorithm