[JAVA] 백준 11052번

11052번 - 카드 구매하기

 

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

public class Main {

	static int[] dp;

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());

		dp = new int[N + 1];

		StringTokenizer st = new StringTokenizer(br.readLine()); // 카드 개수에 따른 카드팩 가격
		dp[1] = Integer.parseInt(st.nextToken());

		for (int i = 2; i <= N; i++) {
			dp[i] = Integer.parseInt(st.nextToken());

			for (int j = 0; j <= i / 2; j++) {
				dp[i] = Math.max(dp[i], dp[i - j] + dp[j]);
			}

		}

		bw.write(String.valueOf(dp[N]));

		bw.flush();
		bw.close();

	}

}

 

정답을 맞춘 풀이방법

1. DP문제로 Bottom - Up 방식을 사용함.  

2. dp[i] 값에 아래와 같은 반복문을 통해 얻은 최대값을 저장함

• dp[i] = ( dp[i-0] + dp[0] ) , ( dp[i-1] + dp[1] ) .... ( dp[i- ( j - 1)] + dp[j-1] ) , ( dp[i] + dp[j] ) 
• N = 4 인경우 : dp[4] , ( dp[3] + dp[1] ) , ( dp[2] + dp[2] ) , ( dp[1] + dp[3] ) 

3. 구하고자 하는 값을 입력 후 출력 함