SoleMap

문제 링크

SoleMap

아이디어

문제에서 주어진 조건을 아래와 같이 단순화할 수 있습니다.

• \(i \rightarrow i+1\) 사이의 도로는 \(W_i\)차선의 양방향 도로
• \(u_i \rightarrow v_i\) 까지 구간내에서 차량은 \(X_j\) 가 지나감
• 구하고자 하는 것은 \(min(\text{각 차로를 지나는 차량 대수의 제곱의 합})\)

먼저, 차량 대수의 제곱의 합은 아래와 같이 표현할 수 있습니다.

• \(\text{해당 구간을 지나는 차량의 대수(C)} = a_1 + a_2 + ... + a_k\) (단, \(k\)은 차로의 개수 )
• \[\text{차량 대수의 제곱의 합} = a_1^2 + a_2^2 + ... + a_k^2\]
  • \(C\)를 임의의 1개의 \(a_i\) 에 할당하는 것과 임의의 2개의 \(a_i\)에 할당했을 경우를 비교해봅시다.
  • \(C^2 \ge (C-a)^2 + (a)^2\) (단, \(a \le C\) ) 임을 만족하므로 \(C\)를 하나의 \(a_i\) 에 할당하는 것 보다, 두 개의 \(a_i\)에 할당하는 것이 최솟값에 가까워지는 것을 알 수 있습니다.
  • 동일한 방법으로 원소의 개수를 확장시켜 나갈 때 최소값이 되는 경우는 C를 k개의 원소에 균등하게 분배하는 것이라는 것을 알 수 있습니다.

두번째로, 각 차로를 지나는 차량의 대수를 합산하는 방법입니다.

구간 \((u_i, v_i)\) 가 주어질 때, \(u_i \rightarrow u_i + 1 , u_i+1 \rightarrow u_i + 2, .... v_i - 1 \rightarrow v_i\) 까지의 모든 구간에서의 차량 대수를 합산하는 것은 쿼리 한 번당 \(N\) 번의 반복 횟수를 가지며 이를 \(M\)번 반복하는 것은 시간 초과입니다.

\(M\)번의 쿼리에서 매번 구간 정보를 업데이트하는 것이 아닌 모든 업데이트 이후에 최종적으로 변화하는 양만큼만 마지막에 한 번 연산하는 것으로 시간 초과를 피할 수 있습니다.

이를 위해서 업데이트 정보 배열 (차분배열) 을 아래와 같이 정의해줍니다.

• passing[i]: i번 이후로 업데이트되는 양
  • 구간 정보 \((u_i, v_i)\) 마다 passing[\(u_i\)] \(\text{+= }x_i\) / passing[\(v_i\)] \(\text{-= }x_i\) 를 해주게 된다면 \(u_i \rightarrow v_i\) 까지의 모든 구간에서의 업데이트 양을 체크할 수 있습니다.

이 후, 누적합을 통해서 최종적으로 모든 구간에서의 차량의 대수를 구할 수 있습니다.

최종적으로 \(O(N)\)의 시간으로 문제를 해결할 수 있습니다.

소스코드

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

public class BOJ_32114 {
    static int N, M, W[];
    static long[] passing;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        N = Integer.parseInt(temp[0]);
        M = Integer.parseInt(temp[1]);
        W = new int[N];
        temp = br.readLine().split(" ");
        for (int i = 1; i < N; i++) {
            W[i] = Integer.parseInt(temp[i - 1]);
        }

        passing = new long[N + 2];
        for (int i = 0; i < M; i++) {
            temp = br.readLine().split(" ");
            int u = Integer.parseInt(temp[0]);
            int v = Integer.parseInt(temp[1]);
            int x = Integer.parseInt(temp[2]);
            passing[u] += x;
            passing[v] -= x;
        }

        for (int i = 1; i <= N; i++) {
            passing[i] += passing[i - 1];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N; i++) {
            long result = 0;
            long d = passing[i] / W[i];
            long r = passing[i] % W[i];
            result = d * d * (W[i] - r) + (d + 1) * (d + 1) * r;
            sb.append(result).append("\n");
        }
        System.out.println(sb);
    }
}