문제

아이디어

배열의 구간에 반복적으로 덧셈을 수행하는 문제다. 직관적으로 구현한다면 O(N*H)의 시간 복잡도가 발생할 것이며, 입력값의 구간으로 보아 이 방법으로 제한 시간 내에 풀이하기는 힘들어 보인다.

태그의 차분 배열 트릭에 대해서 알아보자. 이 차분 배열 트릭을 이용한다면 덧셈 과정을 O(H)에서 O(1)로 줄일 수 있고, 전체 시간 복잡도는 O(N) 안으로 문제를 풀어낼 수 있다.

간단한 개념은 아래와 같다.

1. 배열의 변화를 기록할 차분 배열 d를 할당한다. 이 때 크기는 (원본 배열의 크기) + 1 이다.
2. [a, b] 구간에 c를 더한다고 가정할 때, d[a] += c, d[b+1] -= c을 수행한다.
3. 모든 덧셈에 대해서 차분 배열에 기록했다면, 누적합을 이용해 최종 변화 결과를 구해낸다.

적용은 아래 코드를 통해 알아보자.

소스코드

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

public class Main {
    static int N, H;
    static int[] obstacle;

    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());
        H = Integer.parseInt(st.nextToken());
        obstacle = new int[H + 1];

        int stalactite, stalagmite;
        for (int i = 0; i < N; i += 2) {
            stalactite = Integer.parseInt(br.readLine());
            obstacle[0]++;
            obstacle[stalactite]--;

            stalagmite = Integer.parseInt(br.readLine());
            obstacle[H - stalagmite]++;
            obstacle[H]--;
        }

        int min = Integer.MAX_VALUE, count = 0, sum = 0;
        for (int i = 0; i < H; i++) {
            sum += obstacle[i];
            if(min == sum) count++;
            else if (min > sum) {
                min = sum;
                count = 1;
            }
        }

        System.out.println(min + " " + count);
    }
}

채점결과