문제 링크
문제
티어: 플레 5
알고리즘: 그리디, 정렬
민혁이는 한 도시의 시장으로 취임했다. 민혁이는 제일 먼저 사람들이 전화를 몇 통하는지 알아보려고 한다.
이 도시에는 동서를 잇는 긴 도로가 하나 있고, 그 도로를 따라서 집이 M개 있다. 가장 서쪽에 있는 집의 번호는 1이고, 이 순서대로 진행한다.
전화 감지기는 두 집 사이에 설치할 수 있다. 감지기는 감지기가 설치된 위치로부터 동쪽에 있는 집과 서쪽에 있는 집이 서로 통화하는것을 감지할 수 있다.
하루가 지나고, 민혁이는 감지기를 모두 회수했다. 이제 하루동안 이 도시에 전화가 몇 통있었는지 알아보려고 한다. 감지기가 설치되었던 위치와 각 감지기엔 감지된 전화 통화의 수가 주어졌을 때, 이 마을에서 전화가 적어도 몇 통 있었는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 감지기의 수 N과 집의 수 M이 주어진다. (1 ≤ N ≤ 100,000, N < M ≤ 1,000,000,000)
다음 N개 줄에는 두 수 Pi와 Ci가 주어진다. Pi는 감지기가 설치된 위치이고, Ci는 감지된 전화의 수이다. (1 ≤ Pi < M, 1 ≤ Ci ≤ 1,000,000,000) 감지기가 설치된 위치가 Pi라는 뜻은, Pi와 Pi+1 에 위치한 두 집 사이에 설치되었다는 뜻이다. 같은 장소에 감지기가 여러 개 설치되어 있는 경우는 없다.
출력
첫째 줄에 이 마을에서 하루 동안 전화가 적어도 몇 통 있었는지 출력한다.
풀이
이 마을에서 하루 동안 전화가 적어도 몇 통 있었는지 출려해야 한다.
적어도라는 것은 통화 수를 가능하면 최소로 해야 된다는 뜻이다.
그럴려면 감지기에서는 최대한 많은 감지기를 포함해야 된다.
위치가 왼쪽인 순으로 통화 수를 나열했을 때
4 2 3인 경우
가장 왼쪽에 감지기가 감지한 통화수는 4다. 이때 그 감지기의 왼쪽 집과 3 번째 감지기의 오른쪽 집이 2번 통화했다면, 2 0 1로 줄여줄 수 있다. 단순히 바로 양쪽 집이라고 했을 때는 전체 4번 통화에 0 2 3이지만, 최대한 많은 감지기를 포함했을 때는 2번 통화에 2 0 1이 된다.
직접해 보면 증명은 어렵지 않을 것이다. 핵심은 가능한 가장 많은 감지기를 포함하는 것이다.
그런데 문제점은 그렇게 포함했을 때 가장 작은 통화수를 가진 2 번째 집 때문에 구간이 나눠짐을 알 수 있다. (2 0 1)
매번 이렇게 구간이 나눠지고, 가장 작은 수를 찾는다면, 시간 초과로 문제를 풀 수 없다.
그러면 구간이 생기지 않게 구현할 수 있는 방법은 없을까?
현재 4 2 3에서 첫 번째 감지기는 오른쪽 감지기보다 통화수가 2번 더 많다. 그 말은 2번은 다른 감지기와 포함해서 통화수를 줄여줄 수 없음을 의미한다.
이를 일반화하면 가장 큰 감지기에서 양쪽 감지기 중 큰 값을 맞춰주고, 그 둘을 묶어서 양쪽 감지기 중 큰 값을 맞춰주고를 반복하는 것이고, 결과적으로 구간이 나눠지지 않고 풀 수 있게 된다.
이를 토대로 다음 예제를 풀어보면, (감지기가 0에 가까운 순으로 정렬했을 때)
10 1 9 2
첫 번째 감지기 10은 1과 맞춰준다. 그러면 1 1 9 2가 되며, 전체 통화수는 9다.
다음 두 번째 감지기는 세 번째 감지기인 9와 맞춰준다. 9는 1보다 작기 때문에 1까지 줄여줘야 한다. 그래서 전체 통화수는 9 + 8이며 1 1 1 2가 된다.
여기서 세 번째 감지기는 원래 9였다. 9에서 -> 1이 되는 과정인데 네 번째 감지기가 9보다 작기 때문에 결국 9 -> 2로 맞춰주고(1 1 2 2), 2 2를 같이 1로 내려주면, 전체 통화수는 그대로 17을 유지한다.
그래서 다음 감지기의 값이 더 작을 때(9 -> 2) 그 값이 현재까지 맞춰온 1보다 크다면, 전체 통화수는 17을 유지하고, 만약 맞춰온 수보다 작다면, 결국 그 값으로 줄여줘야 하기 때문에 그 만큼 +를 해주면 된다. 예를 들어 3 3 3 2고 원래 수가 x x 9 2라고 했을 때 9에서 3까지는 오른쪽 2와 묶어서 내려줄 수 없어서 3 3 3을 묶어 +1만 하면 된다. 그래서 결과적으로 (2 2 2 2)가 되는 것이다.
여기서 끝나는 것이 아닌 지금까지 맞춰온 수는 한 번에 묶어서 통화수를 줄여줄 수 있다. 그래서 전체 통화수인 17이고, 1 1 1 1인 상태에서 통화수를 묶어서 줄여주면, 전체 통화수는 18이고, 0 0 0 0인 상태가 된다.
이 풀이의 시간 복잡도는 O(N)이다.
소스 코드
import java.io.*;
import java.util.*;
class Sensor implements Comparable<Sensor> {
long ind;
long c;
Sensor(long ind, long c) {
this.ind = ind;
this.c = c;
}
@Override
public int compareTo(Sensor o) {
if(this.ind < o.ind) {
return -1;
} else if(this.ind > o.ind) {
return 1;
}
return 0;
}
}
public class Main {
static int N, M;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
Sensor[] sensors = new Sensor[N];
for(int i=0; i<N; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
long ind = Long.parseLong(st2.nextToken());
long c = Long.parseLong(st2.nextToken());
sensors[i] = new Sensor(ind, c);
}
Arrays.sort(sensors);
long answer = 0;
long same = sensors[0].c;
for(int i=0; i<N - 1; i++) {
if(sensors[i].c <= sensors[i + 1].c) {
// 2 -> 4인 경우
answer += sensors[i + 1].c - sensors[i].c;
} else {
// 4 -> 2인 경우
if(same > sensors[i + 1].c) {
answer += Math.abs(same - sensors[i + 1].c);
}
same = Math.min(same, sensors[i + 1].c);
}
}
System.out.println(answer + same);
}
}