[백준 - 11052번] 카드구매하기 - 자바(JAVA) 정리 및 해설 & 1일 1DP - 3일차

안녕하세요 오늘 풀어볼 문제는 카드 구매하기입니다. Dynamic Programming 문제를 풀어보도록 하겠습니다.

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

11052번: 카드 구매하기

문제 개요

이문제에서 가장 중요한 포인트는  "금액의 최대값"을 맞춰줘야하기때문에 각 N개의 카드를 샀을의 금액이 최대가 되는 경우를 찾아야합니다. 즉, 각 경우마다의 카드를 살 수 있는 최대 금액을 찾아서 그 값을 저장을 해야합니다. 

 

N 만큼의 카드를 사야한다면,

N = N-1개를 샀을때의 최대 금액+ 1장 살 수있는 금액

 = N-2개를 샀을때의 최대 금액+ 2장 살 수있는 금액

 = N-3개를 샀을때의 최대 금액+ 3장 살 수있는 금액

.............

이런식으로 저 값중에서 가장 큰 금액이 N개의 카드를 사는 최대 금액이 되는 것입니다. 

 

문제는 어떤식으로 풀었나?

역시 이것도 1000 이정도 되기때문에 Top-down으로 풀었지만, 다른분들과 시간적으로 빠르신 분들의 경우 Bottom-UP으로 문제를 풀었습니다. 

 

어쨌든 Top-down 방식으로 구현하려면 탈출 구문과 그에 맞는 재귀 함수를 찾으면 됩니다. 또한 이 최대값을 가지고 있을 배열과 그에 따른 초기화되 되어야하죠.

최대값의 배열이 만약에 값이 재대로 들어가있지않는다면, -> 재귀함수로 들어가게 하고, 최대금액중에서 저희가 유추할수있는 값인 0 혹은 1인 경우를 값 넣어서 탈출 조건을 만들어줍니다.

 

그러면 무난하게 문제가 풀립니다. 

 

/** 2020. 2. 19. 오후 2:19:06
 * @author ventulus95
 */
package codeBaekJoon;

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

public class No11052_CardTrade {
	
	static int cnt[];
	static int arr[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		String tc = br.readLine();
		arr = new int[N+1];
		cnt = new int[N+1];
		StringTokenizer st = new StringTokenizer(tc, " ");
		for(int i =1; i<=N; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.fill(cnt, -1);
		cnt[0] = 0;
		cnt[1] = arr[1];
		System.out.println(func(N));
	}

	private static int func(int n) {
		if(n == 1){
			return cnt[1];
		}
		for(int i =0; i<n; i++){
			if(cnt[i] != -1){
				cnt[n] =Math.max(cnt[n], cnt[i]+arr[n-i]);
			}
			else{
				cnt[n] =Math.max(cnt[n], func(i)+arr[n-i]);
			}
		}
		return cnt[n];
	}

}