[BaekJoon] 11052 카드 구매하기 (Java)

🔗 문제 링크

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

📝 문제 설명

11052번 문제는 Dynamic Programming을 통해 풀이하는 문제이다.

DP를 통해 푸는 방법은 1부터 N까지 배열을 탐색을 하며 여러 조합으로 1을 만들었을 때 가장 큰 수를 1의 최종값으로 결정, 2를 만들었을 때 가장 큰 수를 2의 최종 값으로 결정... 이러한 방식으로 DP배열의 최종 값들을 구해나가면 된다.

아래의 코드는 i만큼의 카드를 뽑을 때 지불해야 할 최대의 금액을 만드는 코드입니다.

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

👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] dp = new int[N+1];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i=1; i<=N; i++) dp[i] = Integer.parseInt(st.nextToken());
		
		for (int i=2; i<=N; i++) {
			int max = dp[i];
			for (int j=0; j<((i/2)+1) ; j++) {
				if ((dp[j] + dp[i-j]) > max) {
					max = dp[j] + dp[i-j];
				}
			}
			dp[i] = max;
		}
        	System.out.println(dp[N]);
	}

}