[백준] 11052 카드 구매하기 - Dynamic Programming / Java

• 문제 링크

11052번: 카드 구매하기

 

• 풀이 과정

n 이 주어지고 0 ~ n 의 범위의 각각의 정수의 합이 n 되는 조합의 규칙성을 찾는 문제.

 

예시로 n = 4 일 때 4 = 0 + 4 = 1 + 3 = 2 + 2 = 3 + 1 의 규칙이 존재하고

이를 더 세분화하면 4 = (4 - 4) + 4 = (4 - 3) + 3 = (4 - 2) + 2 = (4 - 1) + 1 로 나타낼 수 있다.

 

이때 괄호 안의 첫 항과 둘째 항의 값과 대응되는 항을 각각 i, j 로 치환 시 2중 for 문으로 값의 변화를 구현할 수 있으며

반복문의 j 의 범위는 i와 j가 같은 경우는 dp[i] 이고 이는 수식상 제외 가능하므로 1 ~ i - 1 로 지정한다.

 

이에 대한 점화식은 dp[i] = dp[i - j] + dp[j] 이 성립하며,

해당 점화식을 활용한 코드 dp[i] = Math.max(dp[i], dp[i - j] + dp[j]) 로

현재까지 구한 dp[i] 값을 계속해서 비교하여 최대값을 dp[i] 에 갱신한다.

 

최종적으로 dp[n] 의 저장된 최대값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		int[] dp = new int[n + 1];

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			dp[i] = Integer.parseInt(st.nextToken());
			for (int j = 1; j < i; j++)
				dp[i] = Math.max(dp[i], dp[i - j] + dp[j]);
		}

		bw.write(dp[n] + "\n");
		bw.flush();
	}

}