백준 (BOJ) 7983 내일 할 거야 java 그리디

https://www.acmicpc.net/problem/7983

7983번: 내일 할거야

 

 

 

문제만 제대로 이해하면 나름 꿀(?) 문제

 

중요한 건, 당장 내일부터 놀아서 언제까지 놀 수 있는지를 체크해야 한다는 점이다.

 

 

 

다시 보니 굳이 내림차순 정렬할 필요는 없지만, 풀다보니 나도 모르게 그렇게 됐다.

 

뭐 크게 중요한 부분은 아니다. 오름차순으로 해도 뒤에서부터 접근만 하면 되니 . . .

 

여담이 길었다.

 

 

 

제일 마지막 마감일에 끝나는 일부터 접근해야 한다는 점이 중요하다. (시간상 제일 뒤에 끝나는 일)

 

그렇게 해서 일이 제 시간에 끝나면 그 다음 마지막 마감일에 끝나는 일에 접근해서 일이 언제 끝나는지 체크한다.

 

그러다 보면 바로 앞 일의 마감일 보다 더 오래 걸려서 앞 영역을 차지하게 되는 부분이 생긴다.

 

해당 지점을 기억시키고, 계속 진행하면 된다.

그러다 특정 시점에 끝난 작업이 앞 작업의 마감 날짜보다 여유가 생기면,

 

앞 작업을 기준으로 다시 초기화해서 갱신시켜주면 된다.

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] arr = new int[n][2];
        StringTokenizer st;
        for(int i=0; i<n; ++i){
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, (e1, e2) -> {
            return e2[1] - e1[1];
        }); // 내림차순

        int lastEndPoint = arr[0][1]; // 가장 뒷 날 저장
        for(int i=0; i<n; ++i){
            // 마지막으로 끝난 날이 더 뒤에 있어서 여유가 있다면, 새로 시작
            if(arr[i][1] <= lastEndPoint){
                lastEndPoint = arr[i][1] - arr[i][0];
            }
            else{ // 마지막으로 끝난 날이 앞에 위치한다면 거기서 더 감소시킨다.
                lastEndPoint -= arr[i][0]; // 13 - 1 --> 12
            }
        }

        System.out.print(lastEndPoint);

    }
}