1. 문제 링크
https://www.acmicpc.net/problem/1263
2. 문제

요약
- 총 N개의 일을 진행하는데 각 일에 대하여 일을 처리하는데 필요한 시간과 해당 일이 완료되어야 하는 마감시간이 주어졌을 때 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 구하는 문제입니다.
- 입력: 첫 번째 줄에 일의 수 N이 주어지고 다음 줄부터 N개의 줄에는 각 일에 대해 처리하는데 필요한 시간과 처리되어야 하는 마감시간이 주어집니다.
- 출력: 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력합니다. 만약 0시부터 시작해도 일을 못 마친다면 -1을 출력합니다.
3. 소스코드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public int getLatestTime(String[] cases) {
int[] takeTime = new int[cases.length];
int[] endTime = new int[cases.length];
for(int i = 0; i < cases.length; i++) {
StringTokenizer st = new StringTokenizer(cases[i]);
takeTime[i] = Integer.parseInt(st.nextToken());
endTime[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < endTime.length - 1; i++) {
for(int j = i + 1; j < endTime.length; j++) {
if(endTime[i] > endTime[j]) {
int temp = endTime[i];
endTime[i] = endTime[j];
endTime[j] = temp;
temp = takeTime[i];
takeTime[i] = takeTime[j];
takeTime[j] = temp;
}
}
}
int startTime = endTime[0] - takeTime[0];
int curEndTime = endTime[0];
if(startTime < 0) {
return -1;
}
for(int i = 1; i < endTime.length; i++) {
curEndTime += takeTime[i];
if(curEndTime > endTime[i]) {
startTime -= (curEndTime - endTime[i]);
curEndTime -= (curEndTime - endTime[i]);
}
}
if(startTime < 0) {
return -1;
}
return startTime;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int case_num = Integer.parseInt(br.readLine());
String[] cases = new String[case_num];
for(int i = 0; i < case_num; i++) {
cases[i] = br.readLine();
}
br.close();
Main m = new Main();
bw.write(m.getLatestTime(cases) + "\n");
bw.flush();
bw.close();
}
}
4. 접근
- 일을 처리할 때는 마감시간이 빠른 순부터 일을 처리하여 마감시간이 가장 느린 일까지 처리하도록 합니다.
- 그렇기 때문에 입력받은 일들을 마감시간이 빠른 순으로 정렬합니다.
- 모든 일이 하나의 일을 마치고 다음 일을 바로 시작했을 때 마감시간 내에 마쳐진다면 가장 일을 늦게 시작하는 시간은 마감시간이 가장 빠른 일에 대한 (마감시간 - 처리시간)일 것입니다.
- 그렇기 때문에 이를 일을 시작하는 시간으로 정해놓고 일을 처리하면서 일을 마치고 다음 일을 처리할 때 마감시간 내에 일을 마치지 못한다면 그 시간만큼 일을 시작하는 시간을 당깁니다.
- 만약 마감시간이 가장 빠른 일에 대해 마감시간이 처리하는 시간보다 빠르다면 이 일은 0시에 시작해도 일을 마칠 수 없으므로 -1을 출력합니다.
- 그리고 위의 방법대로 마감시간 내에 일을 완수하지 못했을 때 시작하는 시간을 당기는 방법을 사용하여 나온 시작시간이 0보다 작다면 해당 일들 역시 0시부터 시작해도 일을 마칠 수 없기 때문에 -1을 출력합니다.
- 만약 0보다 크거나 같다면 해당 값이 그 시간부터 시작하면 모든 일을 마치면서 최대한 늦게 일을 시작할 수 있는 시간이 됩니다.