[BaekJoon] 1263 시간 관리

1.  문제 링크

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보다 크거나 같다면 해당 값이 그 시간부터 시작하면 모든 일을 마치면서 최대한 늦게 일을 시작할 수 있는 시간이 됩니다.