알고리즘 문제
백준 (BOJ) 7983 내일 할 거야 java 그리디
veryhi
2022. 7. 7. 23:43
https://www.acmicpc.net/problem/7983
7983번: 내일 할거야
내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 출력한다. 가령, 답이 0이면, 내일 과제를 해야 하며, 1 이면, 모레에 과제를 해야 한다.
www.acmicpc.net
문제만 제대로 이해하면 나름 꿀(?) 문제
중요한 건, 당장 내일부터 놀아서 언제까지 놀 수 있는지를 체크해야 한다는 점이다.
다시 보니 굳이 내림차순 정렬할 필요는 없지만, 풀다보니 나도 모르게 그렇게 됐다.
뭐 크게 중요한 부분은 아니다. 오름차순으로 해도 뒤에서부터 접근만 하면 되니 . . .
여담이 길었다.
제일 마지막 마감일에 끝나는 일부터 접근해야 한다는 점이 중요하다. (시간상 제일 뒤에 끝나는 일)
그렇게 해서 일이 제 시간에 끝나면 그 다음 마지막 마감일에 끝나는 일에 접근해서 일이 언제 끝나는지 체크한다.
그러다 보면 바로 앞 일의 마감일 보다 더 오래 걸려서 앞 영역을 차지하게 되는 부분이 생긴다.
해당 지점을 기억시키고, 계속 진행하면 된다.
그러다 특정 시점에 끝난 작업이 앞 작업의 마감 날짜보다 여유가 생기면,
앞 작업을 기준으로 다시 초기화해서 갱신시켜주면 된다.
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);
}
}