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

1. 문제 링크

11052번: 카드 구매하기

 

2. 문제 및 입출력예제

 

3. 문제 풀이

dp 느낌으로 풀었다.

N개의 카드를 제일 비싸게 샀을 때의 가격을 구하는 문제이다.

카드를 살 때마다의 가격을 price 배열에 저장했다.

반복문을 돌리면서 N개를 살 때의 가격을 더해가면서 더 큰 값을 sum 배열에 남겼다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;

public class Main {
	private static int N, price[], sum[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));		
		N = Integer.parseInt(br.readLine());
		price = new int[N+1];
		sum = new int[N+1];
		String[] split = br.readLine().split(" ");

		for(int i=1;i<N+1;i++) {
			price[i] = Integer.parseInt(split[i-1]);
		}

		for(int i=1;i<N+1;i++) {
			for(int j=1;j<=i;j++) {
				sum[i] = Math.max(sum[i], sum[i-j]+price[j]);
			}
		}

		System.out.println(sum[N]);

	}

}