Baekjoon #1263

Baekjoon #1263

1개의 풀이 · Java

문제 원문 보기 ↗

SOLUTION INFO

Java · Main.java

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

public class Main {
    public static void main(String[] args) {
        FastReader rd = new FastReader();
        int N = rd.nextInt();
        int[][] a = new int[N][2];

        for (int i = 0; i < N; i++) {
            a[i][0] = rd.nextInt();
            a[i][1] = rd.nextInt();
        }

        Arrays.sort(a, (n1, n2) -> n2[1] - n1[1]);


        int ans = a[0][1] - a[0][0];
        for (int i = 1; i < N; i++) {
            if (a[i][1] < ans) ans = a[i][1];
            ans -= a[i][0];
        }

        System.out.println((ans < 0) ? -1 : ans);
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}

SOLUTION DESCRIPTION

풀이 설명

1. 그리디 문제. 결과적으로 일을 시작하는 시간을 최대한 늦게 시작하기 위해서는, 주어진 일들을 가능한 빨리 끝내야한다는 것을 의미한다. 즉, 이전의 일이 끝나자마자 바로 다음 일을 시작하는 것이다. 2. 따라서, 이전의 일이 끝난 시간은 `t` 라고 했을 때, `t` + `Ti` ≤ `Si` 가 모두 성립하는지 확인하면 된다. 3. 끝나는 시간을 기준으로 정렬하여, 임의의 시작점을 기준으로 위의 조건이 성사되는지 탐색을 진행한다. a. 내림차순으로 정렬하여, 입력값을 탐색마다 차감하는 방식으로 정답을 구하거나 b. 오름차순으로 정렬하여, 매개변수 탐색을 통해 정답을 구하는 것도 가능하다.

GITHUB COMMUNITY

커뮤니티 평가

GitHub 계정으로 남긴 최신 평가 1건만 반영하며, 데이터는 매일 저장소에 동기화됩니다.

최근 동기화

체감 난이도

아직 평가 없음

첫 난이도 평가를 남겨주세요.

문제 추천

아직 평가 없음

이 문제가 도움이 되었는지 알려주세요.

이 문제 평가하기

GitHub 로그인 후 난이도를 제출하고, 원하는 경우 추천 여부도 함께 남길 수 있습니다.

추천 여부 (선택)

평가하려면 GitHub로 로그인해 주세요.

평가는 자동으로 저장소 Discussion에 기록되므로 Discussion 화면을 직접 열 필요가 없습니다. 같은 문제를 다시 평가하면 기존 평가가 갱신됩니다.

DISCUSSION

댓글

GitHub 로그인 후 작성할 수 있으며 모든 댓글은 이 저장소의 Discussions에 보관됩니다.