백준 20126 자바 - 교수님의 기말고사 (BOJ 20126 JAVA)

문제 : boj20126

 

  각 시험이 서로 겹치지 않는다는 점 때문에 상당히 쉽게 풀 수 있다. 결국 모든 시험이 겹치지 않으므로, 각 시험의 비어있는 구간이 M 이상인지만 확인하면 된다. 즉, i번째 시험을 arr[i] 라고 한다면, arr[i].x - (arr[i-1].x + arr[i-1].y) 의 값이 M보다 크다면 문제의 조건을 만족하는 시간이 된다.

 

  예를들어 다음의 입력을 봐보자.

3 4 20
3 1
7 5
13 3

  위의 그림 중 첫번째 이미지처럼 다른 시험들이 진행될 것이다. 이 때 우리가 확인해야 할 부분은 두번째 이미지의 파란 부분이다. 정렬 후 위에서 제시한 공식대로 진행한다면 어렵지 않게 찾을 수 있다. 답은 16이 될 것이다.

 

  그리고, 그림에서도 나오듯이 주의점은 0-3 구간과 16-S 구간이다. 즉 시작부분과 끝 부분도 체크를 해줘야 한다. 별도로 처리해도 되지만 하나의 로직으로 동작시키는게 더 편하니, 내 경우엔 N+2개로 배열을 만들고, 미리 x=0, y=0과 x=s, y=s인 값을 두 개 추가해준 후 정렬해서 처리했다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;

class Exam implements Comparable<Exam>{
    int x, y;

    public Exam(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Exam o) {
        if (this.x == o.x)
            return this.y - o.y;
        return this.x - o.x;
    }
}

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        int m = nextInt();
        int s = nextInt();

        Exam[] arr = new Exam[n+2];
        arr[0] = new Exam(0, 0);
        for (int i = 1; i <= n; i++)
            arr[i] = new Exam(nextInt(), nextInt());
        arr[n+1] = new Exam(s, s);
        Arrays.sort(arr);

        for (int i = 1; i < arr.length; i++) {
            if (arr[i].x - (arr[i-1].x + arr[i-1].y) >= m) {
                System.out.println(arr[i-1].x + arr[i-1].y);
                return;
            }
        }
        System.out.println(-1);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}