문제 링크
문제
티어: 플레 5
알고리즘: 그리디, 정렬
정우는 생일을 맞아 친구들에게 기프티콘을 N개 선물받았다. 어떤 기프티콘을 언제 쓸지 다 계획을 정해놨는데, 멍청한 정우는 기프티콘에 기한이 있다는 사실을 까맣게 잊고 있었다. 다행히 기프티콘에는 기한 연장 기능이 있다. 한 기프티콘을 한 번 연장할 때마다 기한이 30일씩 늘어난다.
정우는 기프티콘의 기한 연장을 너무 귀찮아하기 때문에, 기한 연장을 최소한으로 하고 싶어한다. 그리고 정우는 강박증이 있어서, 남은 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용할 수 있다. 단, 기한이 가장 적게 남은 기프티콘이 여러 개라면 그 중 아무거나 선택할 수 있다. 하루에 여러 기프티콘을 사용하거나 연장하는 것 모두 가능하다.
최소 횟수로 기한 연장을 하면서 기프티콘을 다 쓸 수 있도록 정우를 도와주자.
입력
첫째 줄에 기프티콘의 수 N이 주어진다.
둘째 줄에 A1, A2, ..., AN가 주어진다. 이는 i번째 기프티콘의 남은 기한이 Ai일이라는 뜻이다.
셋째 줄에 B1, B2, ..., BN가 주어진다. 이는 i번째 기프티콘을 Bi일 뒤에 사용할 계획이라는 뜻이다.
출력
첫째 줄에 정우가 기한 연장을 해야 하는 최소 횟수를 출력한다.
정답이 32비트 정수를 넘을 수 있으므로 유의하라.
제한
- 1 ≤ N ≤ 100,000
- 1 ≤ Ai ≤ 1,000,000,000
- 1 ≤ Bi ≤ 1,000,000,000
풀이
첫째 줄에 정우가 기한 연장을 해야 하는 최소 횟수를 출력해야 한다.
정우는 기프티콘을 사용할 계획을 정해놨기 때문에
계획 순으로 오름차순을 해야 한다.
그리고 첫 번째 계획에 기프티콘을 사용하기 위해서는 현재 남아있는 모든 기프티콘의 기한보다 작거나 같아야지 가능하다.
단순히 첫 번째 기프티콘보다 작은 기한을 순차 탐색으로 찾아서 올려주는 방법이 있는데, N이 10만이기 때문에 불가능한 방법이다.
그러면 순차 탐색외에 다른 방법이 있을지 고민해 보자,
예제 입력 1을 보면,
10 5 4
10 100 30이고, 계획순으로 정렬하면
10 4 5
10 30 100이 된다.
여기서 첫 번째 계획을 실행하기 위해서는 두 번째, 세 번째 기프티콘보다 기한이 높아야 하는데, 이를 한 번에 높여주는 것이 아닌 현재 기한이 정해지고, 다음번 계획에서 전에 기한을 활용한다면, 순차탐색없이 가능하다.
예를 들어 첫 번째 계획은 10이고, 계획은 10일로 정해져 있기 때문에, 연장없이 사용한다. 그리고 이 10을 가지고, 두 번째 계획을 실행하는데, 10보다 큰 값이면서, 가장 작은 값이 되게끔 연장해 준다면, 전체를 탐색하지 않아도 된다. 세 번째 계획에서도 두 번째 계획에서 최종으로 정해진 기한을 활용하면 된다. 이러한 풀이가 가능한 이유는 어차피 전계획에 최종 기한이 현재까지 실행한 모든 계획 중 가장 크기 때문이다.
여기서 처리해야될 중요한 부분이 하나 더 있다. 계획 날짜가 같은 경우다.
계획 날짜가 같은 경우 최대한 전계획에 최종 기한과 차이가 나지 않게끔 유지하는 것이 최선이다.
예를 들어
전계획에 최종 기한이 54인 다음 예제를 보면,
54 2 3 29
10 30 30 30인 경우,
54 59 62 63
10 30 30 30
이렇게 54가 59보다 작으면서 차이가 가장 적고, 그 이후도 같다.
핵심은 최대한 전계획에 최종 기한과 차이가 나지 않게끔 유지하는 것이다.
그래서 같은 계획 날짜인 경우에는 54를 맞춰 주는 최종기한을 구해주고, 오름차순으로 정렬한 것이 최선이 된다.
54 59 62 63
10 30 30 30
이후에 계획이 다른 날짜는 전에 계획에 최종 기한보다 커야되기 때문에 63보다 큰 값이 되게끔 해주면 된다. 또는 같은 날짜라면, 앞에 방법으로 처리해 준다.
이 풀이의 시간 복잡도는 O(NlogN)이다.
소스 코드
import java.io.*;
import java.util.*;
class Gifticon implements Comparable<Gifticon> {
long A, B;
Gifticon(long A, long B) {
this.A = A;
this.B = B;
}
@Override
public int compareTo(Gifticon o) {
if(this.B < o.B) {
return -1;
} else if(this.B > o.B) {
return 1;
}
return 0;
}
}
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
Gifticon[] gc = new Gifticon[N];
StringTokenizer stA = new StringTokenizer(br.readLine());
StringTokenizer stB = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++) {
gc[i] = new Gifticon(Long.parseLong(stA.nextToken()), Long.parseLong(stB.nextToken()));
}
Arrays.sort(gc);
ArrayList<Long> list = new ArrayList<>();
long answer = 0;
long beforeDL = 0; //바로 직전에 사용한 기프티콘의 기한
long curDL = 0;
for(int i=0; i<N; i++) {
if(beforeDL - gc[i].A > 0) {
//beforeDL이 크다면 현재 A 값을 높여줘야 됨.
long need = beforeDL - gc[i].A;
curDL = gc[i].A + ((need / 30) * 30);
answer += need / 30;
if(need % 30 != 0) {
//0이 아니라면 연장 횟수 + 1추가
curDL += 30;
answer += 1;
}
} else {
//beforeDL이 더 작다면 A를 높여줄 필요가 없음
curDL = gc[i].A;
}
//여기부터는 curDL 최소한으로 더 큰 기한을 가지고 있음.
//이번에는 계획에 맞춰줘야 됨.
if(gc[i].B - curDL > 0) {
//기한이 더 작다면 기한을 더 늘려줘야 됨
//100 - 5 = 95 -> 95 / 30 = 3, 5 + 3 * 30 = 95 + 30 = 125
long need = gc[i].B - curDL;
curDL += (need / 30) * 30;
answer += need / 30;
if(need % 30 != 0) {
curDL += 30;
answer += 1;
}
}
list.add(curDL);
if(i != (N - 1)) {
if(gc[i].B != gc[i + 1].B) {
Collections.sort(list);
beforeDL = list.get(list.size() - 1);
list = new ArrayList<>();
}
}
}
System.out.println(answer);
}
}