티떱랜드 열차 어색함 최소화 문제

문제 설명

N명의 사람들이 한 줄로 서 있고, K개의 열차에 나누어 탑승해야 한다. 각 열차는 연속된 사람들을 태워야 하며, 각 열차의 어색함은 탑승한 사람들 간의 어색한 정도 ( u_{ij} )의 합으로 정의된다. 모든 열차의 어색함의 합을 최소화하도록 사람들을 나누는 방법을 찾아야 한다.

핵심 아이디어

1. 어색함 계산:

   • 어색한 정도 ( u_{ij} )는 ( i )번 사람과 ( j )번 사람 사이의 어색함을 나타내며 대칭 행렬 ( U )로 주어진다.
   • ( D2[i][j] ): 구간 ( [i, j] )에서 한 열차에 탑승했을 때의 어색함 합.

2. 다이나믹 프로그래밍:

   • ( D[t][j] ): ( t )개의 열차를 사용해 ( 1 )번부터 ( j )번 사람까지 나누었을 때 최소 어색함 합.
   • 점화식:
     [
     D[t][j] = \min_{k < j} { D[t-1][k] + D2[k+1][j] }
     ]
   • 초기 조건:
     [
     D[1][j] = D2[1][j]
     ]

3. 분할정복 최적화:

   • ( D[t][j] )를 계산할 때, 최소값을 만드는 ( k )는 ( j )의 범위 내에서 단조 증가한다는 점을 이용.
   • 이 특성을 활용하여 계산량을 줄임.

코드

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

public class Main {
    static final int INF = Integer.MAX_VALUE;
    static int N, K;
    static int[][] U;
    static int[][] D1, D2, D, P;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        U = new int[N + 1][N + 1];
        D1 = new int[N + 1][N + 1];
        D2 = new int[N + 1][N + 1];
        D = new int[K + 1][N + 1];
        P = new int[K + 1][N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                U[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        preprocess();

        for (int i = 1; i <= N; i++) {
            D[1][i] = D2[1][i];
        }

        for (int t = 2; t <= K; t++) {
            solve(t, t, N, t - 1, N - 1);
        }

        System.out.println(D[K][N]);
    }

    static void preprocess() {
        for (int i = 1; i <= N; i++) {
            D1[i][1] = U[i][1];
            for (int j = 2; j <= N; j++) {
                D1[i][j] = D1[i][j - 1] + U[i][j];
            }
        }

        for (int i = 1; i <= N; i++) {
            D2[i][i] = 0;
            for (int j = i + 1; j <= N; j++) {
                D2[i][j] = D2[i][j - 1] + (D1[j][j] - D1[j][i - 1]);
            }
        }
    }

    static void solve(int t, int st, int en, int Pmn, int Pmx) {
        if (st > en) return;

        int mid = (st + en) / 2;
        D[t][mid] = INF;

        for (int sep = Pmn; sep <= Math.min(Pmx, mid - 1); sep++) {
            int cost = D[t - 1][sep] + D2[sep + 1][mid];
            if (cost < D[t][mid]) {
                D[t][mid] = cost;
                P[t][mid] = sep;
            }
        }

        solve(t, st, mid - 1, Pmn, P[t][mid]);
        solve(t, mid + 1, en, P[t][mid], Pmx);
    }
}

코드 설명

1. 행렬 (D1, D2) 계산:

   • (D1[i][j]): (i)번 사람이 (j)번 사람까지 함께 탑승했을 때의 어색함 합.
   • (D2[i][j]): 구간 ([i, j])의 총 어색함 합.

2. 다이나믹 프로그래밍:

   • (D[t][j]): (t)개의 열차를 사용해 1번부터 (j)번 사람까지 나누었을 때의 최소 어색함 합.

3. 분할정복 최적화:

   • (D[t][j])를 계산할 때, 가능한 범위를 이분 탐색으로 줄임.

So...

이 코드는 분할정복 최적화를 통해 DP의 계산량을 크게 줄여 O(K⋅N⋅logN)에 문제를 해결한다. 이 문제를 풀며 어색함 합산 방식과 구간 최적화를 고려하며 효율적인 해결 방안을 설계한 점이 중요하다. 이러한 방식은 DP와 최적화가 결합된 전형적인 고급 알고리즘 문제로, 실무에서도 효율적 데이터 분할과 집계에 응용 가능하다.