문제 링크
문제
티어: 골드 1
알고리즘: 그리디, 정렬, 누적합
승원이는 미술품 N개를 가지고 있다. 각각의 미술품은 1번부터 N번까지 번호가 매겨져 있다. i번 미술품의 크기는 Ai, 가치는 Bi로 나타낸다.
오늘은 승원이의 저택 1층에서 미술품을 전시하려고 한다. 승원이는 아래 조건을 만족하는 미술품을 골라서 전시하려고 한다.
- 전시할 미술품 중에서 가장 큰 크기를 Amax, 가장 작은 크기를 Amin 이라고 한다. 전시할 미술품의 가치의 합을 S라고 한다.
- 이때, S − (Amax − Amin) 가 가장 커야 한다.
승원이가 가지고 있는 미술품 N개의 크기와 가치가 주어졌을 때, S − (Amax − Amin) 의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 승원이가 가지고 있는 미술품의 개수 N (2 ≤ N ≤ 500,000)이 주어진다.
둘째 줄부터 N개의 줄에 미술품의 크기 Ai와 가치 Bi가 1번 미술품 부터 순서대로 주어진다. (1 ≤ Ai ≤ 1,000,000,000,000,000 = 1015, 1 ≤ Bi ≤ 1,000,000,000)
출력
첫째 줄에 S − (Amax − Amin) 의 최댓값을 출력한다.
풀이
S − (Amax − Amin) 의 최댓값을 출력해야 한다.
작품을 크기순으로 오름차순 정렬하고, Amax와 Amin을 정해보자, 그러면 그 가운데는 무조건 포함하는 것이 이득이다. 왜냐하면 (Amax - Amin)은 변하지 않는데, S만 증가하기 때문이다.
결국 연속된 모든 구간을 구해서 그 구간 중 최댓값을 출력하면 된다.
크기순으로 정렬된 작품을 0 번째 인덱스부터 N-1까지 누적합을 구해놓으면 모든 구간은 O(1)로 구할 수 있다.
예를 들어 prefix[5] = 15이고, prefix[2] = 10일 때 2 ~ 5구간은 prefix[5] - prefix[1]이 된다.
그러면 이제 연속된 모든 구간을 탐색해서 최댓값을 알아내야 하는데, 당연히 모든 구간은 O(N^2)이 필요하기 때문에 시간초과로 불가능하다.
일단 모든 구간을 구한다고 생각하고, 나열해 보면,
1 - 1,
1 - 2
2 - 2,
1 - 3
2 - 3
3 - 3
이렇게 구간을 나타낼 수 있고,
1 - 2
2 - 2
에서 2 - 2가 더 크다면,
1 - 3
2 - 3
3 - 3
에서는 2 - 3과 3 - 3만 비교하면 된다.
왜냐하면 1 - 2, 2 - 2는 이미 비교를 해서 2 - 2가 크다는 것을 알았고, 여기서 끝이 3으로 변한다 해도, 그 증가값은 똑같기 때문이다. 증명해 보면, 쉽게 이해될 것이다.
(여기서 3 - 3은 새로 추가된 구간이기 때문에 비교해줘야 한다.)
그러면 다시 2 - 3이 더 크다면
1 - 4
2 - 4
3 - 4
4 - 4
에서는 2 - 4와 4 - 4를 비교해서 큰 값을 구하면 된다. 여기서 구한 값은 바로 다음 오른쪽이 5인 구간에서 사용된다. (1 - 5, 2 - 5, 3 - 5, 4 - 5, 5 - 5)
그러면 우리가 끝을 기준으로 각 끝 점마다 가장 큰 값을 구했을 것이고, 그 값의 개수는 N개가 존재할 것이다.
이 중 가장 큰 값이 결국 S − (Amax − Amin) 의 최댓값이 되는 것이다.
이 풀이의 시간 복잡도는 O(NlogN)이다. (정렬 시간 복잡도가 가장 큼)
소스 코드
import java.io.*;
import java.util.*;
class Art implements Comparable<Art> {
long A, B;
Art(long A, long B) {
this.A = A;
this.B = B;
}
@Override
public int compareTo(Art o) {
if(this.A < o.A) {
return -1;
} else if(this.A > o.A) {
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());
Art[] arts = new Art[N + 1];
for(int i=1; i<=N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
arts[i] = new Art(Long.parseLong(st.nextToken()), Long.parseLong(st.nextToken()));
}
arts[0] = new Art(0, 0);
Arrays.sort(arts);
long[] prefix = new long[N + 1];
prefix[1] = arts[1].B;
for(int i=2; i<=N; i++) {
prefix[i] = prefix[i - 1] + arts[i].B;
}
int minIndex = 1;
long[] answerArr = new long[N + 1];
answerArr[1] = prefix[1];
for(int i=2; i<=N; i++) {
answerArr[i] = (prefix[i] - prefix[minIndex - 1]) - (arts[i].A - arts[minIndex].A);
if(answerArr[i] <= arts[i].B) {
answerArr[i] = arts[i].B;
minIndex = i;
}
}
long answer = 0;
for(int i=1; i<=N; i++) {
answer = Math.max(answer, answerArr[i]);
}
System.out.println(answer);
}
}