[백준, DP, JAVA] P.11052 카드 구매하기

문제

풀이

1. 다이나믹 프로그래밍을 적용할 수 있는 문제인지 확인
- 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹치는지?
   (Overlapping SubProblem)

- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

2. 자료구조에(실무를 제외하고 일반적인 문제 해결과정에서는 보통 배열사용) 어떤 값을 저장할 것인지 문장으로 정리
- memoization[N] = "N개의 물건을 묶음 및 단일 조합을 통해 구매하여 지불할 수 있는 최대 금액"

3. memoization[N]의 값을 어떤 규칙을 통해 찾을 수 있는지 생각하기(점화식 or 아이디어)
- memoization[0] = 0
- memoization[1] = memoization[0] + cards[1], memoization[1] 중 최대
- memoization[2] = memoization[0] + cards[2], memoization[1] + cards[1], memoization[2] 중 최대
- memoization[N] = memoization[1] + cards[N-1],......,memoization[N-1] + cards[N-(N-1)], memoization[N] 중 최대
N으로 커질수록 비교해야 하는 경우의 수가 늘어남 재귀 혹은 반목문을 통해 규칙성 부여

4. 구현 코드
재귀를 활용하여 구현하였다.

import java.util.Scanner;

public class Main {
	static int[] cards;
	static int N;
	static int[] memoization;
	static int MAX = Integer.MIN_VALUE;

	public static void main(String[] args) {
		Scanner scr = new Scanner(System.in);

		N = scr.nextInt();
		cards = new int[N + 1];
		memoization = new int[N+1];

		for (int i = 1; i <= N; i++) {
			cards[i] = scr.nextInt();
		}
		
		for(int i=0;i<=N;i++) {
			memoization[i] = 0;
		}

		int result = recursive(N);

		System.out.println(result);
	}

	public static int recursive(int count) {
		if(count == 0)
			return 0;
		if(memoization[count] > 0)
			return memoization[count];
		
		for(int i=1;i<=count;i++) {
			memoization[count] =  Math.max(memoization[count], recursive(count-i) + cards[i]);
		}
		
		return memoization[count];
	}
}

 

5. 느낀점
다른 알고리즘들은 많이 풀어보았으나, 다이나믹 프로그래밍을 이제야 제대로 시작하게 된것이 아쉽다. 앞으로 꾸준히 노력하여 내 머리를 
컴퓨터 회로처럼 바꿀수 있도록 노력해야겠다.