백준 11052번 : 카드 구매하기 (Java)

 문제

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

11052번: 카드 구매하기

11052 카드 구매하기

 

 구현 방법

i개가 가질 수 있는 모든 경우를 구하여 최댓값을 구해주었습니다.

입력되는 값을 해당 위치에 저장한 뒤 그 값이 가질 수 있는 최댓값을 구하여 다음 최댓값을 구할 때 사용하게 됩니다.

 

예제를 예를 들면 

4
1 5 6 7

< 1개일 때 >        
1개 : 1       
-> 1 

< 2개일 때 >        
1개 + 1개 : 2       
2개 : 5         
-> 5    

< 3개일 때 >      
1개 + 2개 : 6         
3개 : 6         
-> 6        

< 4개일 때 >         
1개 + 3개 : 7        
2개 + 2개 : 10        
4개 : 7         
-> 10

총 10원임을 알 수 있습니다.

 

 구현 코드

package BOJ.Silver;

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

public class B11052_카드구매하기 {
	public static void main(String[] args) throws IOException {
		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());
		dp[1] = Integer.parseInt(st.nextToken());
		for (int i=2;i<=N;i++) {
			dp[i] = Integer.parseInt(st.nextToken());
			// i가 가질 수 있는 최대값 구하기
			int start = 1, end = i-1;
			while(start<=end) { // 가질 수 있는 모든 경우의 수
				dp[i] = Math.max(dp[i], dp[start++]+dp[end--]);
			}
		}
		System.out.println(dp[N]);
	}
}

 

정답!