<Algorithm> 213. 조짜기(BOJ)

1. 2229번 조짜기(BOJ)

   사용 알고리즘 :  DP

• 처음에 209. 파일합치기(BOJ) 이문제와 유사하다는 느낌을 받아 비슷한 방법으로 풀어보았다.

• 차이는 이문제는 기준점으로 부터 처음까지 탐색하여 결과를 내기 떄문에 1차원 DP만으로 풀 수 있었다.

문제에 대한 접근&생각

1. 조를 만드는데 가장 작은값과 큰값의 차이가 큰 경우 -> 결과조건!
2. 너무 많은 경우의 수 -> 완전탐색X, DP! 
3. 나이순으로 정렬되어 최대한 나이차이가 적게 나게 조를 구성 -> 순차적으로 조를 구성 -> 기준을 잡고 역탐색!

코드 

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n+1];
        int[] dp = new int[n+1];
        /***************************
         * 이중반복을 통해 처음부터 반복하고
         * 다른 반복은 앞의 반복의 인수를
         * 기준으로 삼아서 반대로 반복한다.
         * 이떄 DP를 이용하여 값을 누적하고
         * 최댓값인지 판단하여 값을 변경한다.
         ***************************/
        for(int i = 1; i <= n; i++) {
            arr[i] = sc.nextInt();
        }
        for(int i = 1; i <= n; i++) {
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int j = i; j > 0; j--) {
                max = Math.max(max, arr[j]);
                min = Math.min(min, arr[j]);
                dp[i] = Math.max(dp[i], dp[j-1]+(max-min));
            }
        }
        
        System.out.println(dp[n]);
    }
}