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

풀이 아이디어

과제 소요일과 과제 마감일을 하나의 배열로 받는다.
과제 마감일이 늦은 순서로 즉 내림차순으로 정렬하고
만약 과제 마감일이 같다면 과제 소요일이 적은 순으로 정렬한다.
예시)
[[2,8], [1,13], [2,13], [3,10]]을 정렬하면
[[1, 13], [2, 13], [3, 10], [2, 8]]가 된다.

현재 n일 후 일해야하는 날짜 startDeadline을 설정하고
배열 0번째의 (과제 마감일 - 과제 소요일)을 할당한다.
이후 startDeadline < {다음과제 마감일}이면
startDeadline - {다음과제 소요기간}을 빼준다.
다른 경우로는 startDeadline >= {다음과제 마감일}이면
startDeadline = {다음과제 마감일} - {다음과제 소요기간}으로 갱신해준다.

예시)
1. startDeadline = 13-1 = 12
2. 12와 [2,13]을 비교 12<13이므로 startDeadline = 12-2 = 10
3. 10과 [3,10]을 비교 10==10이므로 startDeadline = 10-3 = 7
4. 7과 [2,8]을 비교 7<8이므로 startDeadline = 7-2 = 5
5. 정답 5를 출력

트러블슈팅

배열을 사용해서 메모리초과

처음에는 가장 늦은 과제 마감일이 d면
boolean[d]라는 배열을 만들어서 과제하는 날마다 false를 true로
바꿔줄려고 했는데 배열을 사용하니 메모리 초과가 발생했다.
원인이 뭔가 읽어보니 boolean[d]에서 di, ti가 $10^{9}$까지 주어져서 메모리 초과가 발생하는 것으로 보인다.

해결

배열이 아닌 DP적으로 값을 갱신해주자.

풀이 스니펫

원소가 2개인 입력값을 정렬하기

배열을 정렬할 때 비교연산자인 compare를 override해서
원소가 2개일 때도 내림차순, 오름차순을 정렬할 수 있다.
아래 코드는 d,t를 저장한 배열 int[][] task에서
task[0] = d (과제 소요기간)
task[1] = t (과제 마감일)일때
과제 마감일 task[1]을 내림차순으로 정렬하고
같은 마감일이 있는 경우 과제 소요기간 task[0]을 오름차순으로 정렬한 코드이다.

예시)
[[2,8], [1,13], [2,13], [3,10]]을 정렬하면
[[1, 13], [2, 13], [3, 10], [2, 8]]가 된다.

int[][] task = new int[n][2]

// 과제 마감일이 늦은 순으로 정렬, 과제 마감일이 같다면 과제 소요일이 적은 순으로 정렬
Arrays.sort(task, new Comparator<int[]>(){
    @Override
    public int compare(int[] o1, int[] o2){
        if(o1[1] == o2[1]){
            return o1[0] - o2[0]; // 오름차순
        }
        return o2[1] - o1[1]; // 내림차순
		// return o1[1] - o2[1]; // 오름차순
    }
});

2차원 배열을 문자열로 출력하기

Arrays.deepToString(이차원 배열) 메서드를 사용하면
이차원 배열의 안의 값까지도 문자열로 출력할 수 있다.
문제 풀이에 사용한 건 아니고
테스트 과정에서 배열이 제대로 정렬되었는지 확인하는 용도로 사용했다.

int[][] task = new int[n][2]

System.out.println(Arrays.deepToString(task));

[[1, 13], [3, 10], [2, 8]]

풀이 코드

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

public class _7983 {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n: 과제의 수
        int n = Integer.parseInt(br.readLine());
        int[][] task = new int[n][2];
        
        // d: 과제 소요일, t: 과제 마감일
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            task[i][0] = Integer.parseInt(st.nextToken());
            task[i][1] = Integer.parseInt(st.nextToken());
        }
        // 과제 마감일이 늦은 순으로 정렬, 과제 마감일이 같다면 과제 소요일이 적은 순으로 정렬
        Arrays.sort(task, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                if(o1[1] == o2[1]){
                    return o1[0] - o2[0];
                }
                return o2[1] - o1[1];
            }
        });

        // 과제 마감일이 늦은 순으로 정렬된 task 배열을 순회하며 쉴 수 있는 날 계산 
        int startDeadline = task[0][1]-task[0][0];
        for(int i=1; i<n; i++){
            if(startDeadline < task[i][1]){
                startDeadline = startDeadline - task[i][0];
            }
            else{
                startDeadline = task[i][1] - task[i][0];
            }
        }
        System.out.println(startDeadline);
    }
}