[백준 2229번] 조 짜기

문제 링크: 2229번 조 짜기

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

 

1000 이하라는 N의 범위를 고려할 때 O(N²) 알고리즘이 떠오를 법하지만, O(N)으로도 풀 수 있는 문제이다. 일단 학생의 순서를 바꿀 수 없는 상태에서 조를 나누는 것이라는 점에 착안하여, 고려 대상 학생을 한 명씩 추가해나가면서 해당 학생을 ①마지막으로 만든 기존의 조에 포함시킬지, ②이전 학생과 함께 새로운 조를 만들지를 나누어 DP를 적용시킬 수 있다.

 

다만, 이 문제를 처음 읽으면 다음과 같은 생각을 할 수 있다. "한 조 내에서 최솟값과 최댓값의 차이만을 고려할 것이니, 3명 이상이 하나의 조를 이루는 것은 비효율적이다". 결론부터 말하자면 거짓이다. 당장 1, 2, 3의 예시만 생각해보더라도, 1, 2, 3은 하나의 조가 되어야 한다.

또한 2, 3, 1의 예시를 고려해보자. 2번째 학생까지 고려했을 때, 2, 3은 하나의 조를 이루어야 한다. 하지만 세 번째 학생까지 고려한다면 (2), (3, 1)과 같이 조를 이루는 편이 가장 이득이다. 즉 i번째 학생의 도입은, i - 1번째 학생을 이전 조에서 빼내어 새로운 조를 만들지 말지 고민하게 한다.

 

sum[i]는 i번째 학생까지 고려했을 때 최댓값을 의미한다. mem[i][0]은 i번째 학생까지 고려했을 때 마지막 조의 최솟값을, mem[i][1]은 i번째 학생까지 고려했을 때 마지막 조의 최댓값을 저장한다.

 

예시로 주어진 경우를 생각해보자.

 

1번 학생: 2
2번 학생: 5
3번 학생: 7
4번 학생: 1
5번 학생: 3
6번 학생: 4
7번 학생: 8
8번 학생: 6
9번 학생: 9
10번 학생: 3

 

1번 학생까지 고려했을 때

mem[1][0]과 mem[1][1]은 무조건 arr[1]과 같을 수밖에 없다. 그리고 sum[1]은 아직 1명의 학생밖에 고려하지 않았으므로 0으로 고정된다.

 

2번 학생까지 고려했을 때

1번, 2번 학생은 무조건 같은 조에 편성되는 것이 이득이다. 두 명이 각기 다른 조에 편성된다면 한 조에 한 명씩 배정되어 각각 "잘 짜여진 정도"가 0이기 때문이다. 따라서 mem[2][0]에는 1번 학생 점수와 2번 학생 점수의 최솟값, mem[2][1]에는 1번 학생 점수와 2번 학생 점수의 최댓값이 들어간다. sum[2]도 별다른 어려움 없이 구할 수 있다.

 

3번 학생까지 고려했을 때

①2번 학생이 있는 기존의 조에 3번 학생을 포함시킬지(이 때 sum[3]을 sum1이라고 하자)

원래와 같이 조의 구성이 (2, 5)였다면, "잘 짜여진 정도"는 3이다. 하지만 3번 학생을 기존의 조에 포함시켜, 조의 구성이 (2, 5, 7)이 된다면, "잘 짜여진 정도"는 5가 된다. 그렇다면 3번 학생을 추가함으로써 sum1은 sum[2]에 비해 5-3=2만큼 증가하는 것이므로, sum1 = sum[2] + 2이다. 요컨대 이전 그룹들의 합도 유지하고 있어야 하므로 5를 바로 대입해서는 안된다.

 

②2번 학생, 3번 학생을 새로운 조로 묶을지(이 때 sum[3]을 sum2라고 하자)

sum2 = sum[i - 2] + max(arr[i - 1], arr[i]) - min(arr[i - 1], arr[i]);

(i-1=2)번 학생과 (i=3)번 학생을 새로운 조로 묶을 것이므로 기존의 합은 sum[i - 2]를 이용해야 한다.

그리고 새로운 조는 2명뿐이므로, (i-1=2)번 학생과 (i=3)번 학생만 고려하여 "잘 짜여진 정도"를 구하면 된다.

sum2라 함은 지금까지의 합이므로 이 둘을 더해준다.

 

③2번 학생은 그대로 두고 3번 학생부터 새로운 조를 이룰지

3번 학생이 새로운 조를 만들어봤자 해당 조의 "잘 짜여진 정도"는 0이므로 sum[3] = sum[2]가 되어 고려할 필요가 없다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        if (n == 1) {
            System.out.println(0);
            return;
        }
        
        int[][] mem = new int[n + 1][2];
        int[] sum = new int[n + 1];
        mem[1][0] = arr[1];
        mem[1][1] = arr[1];
        mem[2][0] = min(arr[1], arr[2]);
        mem[2][1] = max(arr[1], arr[2]);
        sum[2] = mem[2][1] - mem[2][0];

        for (int i = 3; i <= n; i++) {
            // attach to prev group
            int newMin = min(arr[i], mem[i - 1][0]);
            int newMax = max(arr[i], mem[i - 1][1]);
            int add = newMax - newMin - (mem[i - 1][1] - mem[i - 1][0]);
            int sum1 = sum[i - 1] + add;

            // detach from prev group
            int sum2 = sum[i - 2] + max(arr[i - 1], arr[i]) - min(arr[i - 1], arr[i]);

            if (sum1 > sum2) {
                mem[i][0] = newMin;
                mem[i][1] = newMax;
                sum[i] = sum1;
            } else {
                mem[i][0] = min(arr[i - 1], arr[i]);
                mem[i][1] = max(arr[i - 1], arr[i]);
                sum[i] = sum2;
            }
        }

        System.out.println(sum[n]);
    }

    static int min(int a, int b) {
        return a < b ? a : b;
    }

    static int max(int a, int b) {
        return a > b ? a : b;
    }
}