[백준, DP, JAVA] P.2299 조짜기

1. 아이디어

1. 입력값을 받을 때마다 해당 번째 위치에서 1번째까지 반복하며 조를 만들면서 최적의 값을 비교하여 가장 좋은 값을 선택

(1)우선 dp[0] = 0, dp[1] = 0으로 초기화 해줍니다. 0번째와 1은 자기자신이기 때문에 값의 차이가 자기자신 - 자기자신 = 0

(2)dp[2]인 경우
[1] 자기자신 그루핑한 값 + 직전의 그루핑한 값 중 최적의 값
[2] 자기자신과 바로 직전값 1과 그루핑한 값 + 1의 직전의 그루핑한 값중 최적의 값

dp[3]인 경우
[1] 자기자신 그루핑한 값 + 2에서 그루핑한 값 중 최적의 값
[2] 자기자신과 바로 직전값 2와 그루핑한 값 + 1에서부터 그루핑한 값중 최적의 값
[3] 자기자신과 1번째 까지 그루핑한 값 + 0에서부터 그루핑한 값중 최적의 값

dp[N]인 경우
[1] 자기자신 그루핑한 값 + 자기자신-1에서 그루핑한 값중 최적의 값
[2] 자기자신에서 자기자신-1 그루핑한 값 + 자기자신-2에서 그루핑한 값중 최적의 값
...
[N-1] 자기자신에서 + 자기자신 - (N-1)에서 그루핑한 값 + 자기자신 - (N-1) -1 에서 그루핑한 값중 최적의 값  
여기서 -(N-1)-1은 결국 N입니다.

이제 위에 dp[N]인 경우 이부분을 첫번째 for문으로 생각하고 [1]...[N-1]을 첫번째 for문안에 있는 중첩 for문으로 취급

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scr = new Scanner(System.in);
		
		int N = scr.nextInt();
		int[] arr = new int[N+1];
		int[] dp = new int[N+1];
		int optimalValue = 0;
		dp[0] = 0;
		dp[1] = 0;
		int max = 0;
		
		for(int i=1;i<=N;i++) {
			arr[i] = scr.nextInt();
			
			for(int j = i-1;j>=1;j--) {
				max = Math.max(max,Math.abs(arr[i]-arr[j]) + dp[j-1]);
			}
			
			dp[i] = max;
			optimalValue = dp[i];
		}
		
		System.out.println(optimalValue);
	}
}

완벽히 제 아이디어는 아닙니다. 결국 완전한 힘으로 풀지는 못했습니다. 앞으로는 고민하다가 일단 아이디어가 전혀
떠오르지 않을때는 다른분 아이디어도 어느정도 보면서 익히기로 했습니다. 결국 저는 일반인이기에 똑똑한 선배들의 여러 아이디어들을 머리에 넣다보면 나중에 자연스럽게 체득해서 제 아이디어처럼 꺼내게 되겠죠... 그날이 올때까지
부단히 체득화하겠습니다.