그리디 문제 하나 풀었다.
https://www.acmicpc.net/problem/1263
시간 관리 성공
2 초 | 128 MB | 3542 | 1483 | 1253 | 42.503% |
문제
진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.
진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.
진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.
입력
첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti와 Si가 입력된다.
출력
진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.
제한
- 1 ≤ N ≤ 1,000
- 1 ≤ Ti ≤ 1,000
- 1 ≤ Si ≤ 1,000,000
예제 입력 1 복사
4
3 5
8 14
5 20
1 16
예제 출력 1 복사
2
진영이가 제일 늦잠을 자는 경우는 마지막으로 종료되어야 하는 업무를 기준으로 하나씩 업무를 끝내면 종료되는 시간을 알 수 있다
결국 마지막 종료 업무부터 최적의 해를 찾아가는 그리디 알고리즘 문제다.
우선순위 큐를 이용하여 (업무 늦게 끝나며 / 짧은 업무시간 순)으로 받아서 하나씩 제거해나갔다.
처음에 하루로 생각해서 24시간설정을 했다 계속 틀려서 확인해보니 제한 시간이 24시간이 넘는거였다
최대 업무 시간을 마지막 업무 종료시간으로 설정해서 처리하는 정답이 되었다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
/**
* https://www.acmicpc.net/problem/1263
*/
public class Main {
public static void main(String[] args) throws IOException {
greedy();
}
public static void greedy() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(((o1, o2) -> {
if (o1[1] == o2[1]) {
return o1[0] - o2[0];
} else {
return o2[1] - o1[1];
}
}));
for (int i=0 ; i < N; i++) {
st = new StringTokenizer(br.readLine());
priorityQueue.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
}
int time = priorityQueue.peek()[1];
while (!priorityQueue.isEmpty()) {
if (priorityQueue.peek()[1] < time) {
time--;
continue;
}
if (priorityQueue.peek()[1] >= time) {
int[] work = priorityQueue.poll();
time -= work[0];
}
}
System.out.println(time >= 0 ? time : "-1");
}
}
결과
'Coding Test' 카테고리의 다른 글
백준 입국심사(3079) (0) | 2024.03.05 |
---|---|
백준 개똥벌레 (3020) (0) | 2024.03.04 |
백준 숌 사이 수열(1469) (0) | 2024.03.02 |
백준 로프(2217) (0) | 2024.03.01 |
백준 회의실 배정 성공(1931) (0) | 2024.02.29 |