[백준] 11052번 카드 구매하기 (다이나믹 프로그래밍_JAVA)

반복문 하나로 처리하려다가

그냥 이중반복문으로 푸니까 됐다!

n이 1000이었는데 10000으로 잘 못 본 나

반성하쟈...

 

 

---

문제

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

11052번: 카드 구매하기

 

 

---

설계

알고리즘[접근 방법] : DP

2차원 배열을 만들고, 누적합을 만든다.

현재 인덱스를 기준으로, 인덱스가 나올 수 있는 덧셈을 모두 계산해서 비교한다.

 

예를 들어, 현재 인덱스가 6이라면,

1) arr[0][6]

2) arr[0][5]+arr[0][1] 

3) arr[0][4]+arr[0][2] 

4) arr[0][3]+arr[0][3]

다음의 값들을 비교해서  제일 큰 값을 arr[1][6]에 저장한다.

 

그럼 arr[1][n]에 최종 값이 저장된다!

 

 

 

---

코드

import java.util.Arrays;
import java.util.Scanner;

public class Test_11052_카드구매하기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//배열 크기 입력받기
		int n = sc.nextInt();
		
		//dp배열 생성 및 값 입력받기
		int[][] arr = new int[2][n+1];
		for(int i=1; i<n+1; i++) {
			arr[0][i]=sc.nextInt();
		}
		
		
		//누적합 만들기
		for(int i=1; i<n+1; i++) {
			int tmp = arr[0][i];	//현재 값
			
			int max=0;
			for(int j=i-1; j>=i/2; j--) {	//현재 인덱스 i가 나오는 j의 값을 더하기
				max = Math.max(max, arr[1][j]+arr[1][i-j]);
			}
			
			arr[1][i]=Math.max(tmp, max);
		}
		
		//출력
		System.out.println(arr[1][n]);
		
	}
}

 

 

(❁´◡`❁)

끝!