문제 링크
문제
티어: 골드 2
알고리즘: 그리디, 정렬
입력
첫 번째 줄에 격자판의 크기 n, 말의 수 k, 칸막이의 수 d가 공백을 사이로 두고 주어집니다.
두 번째 줄에는 k개의 정수 p1, p2, ..., pk가 공백을 사이로 두고 주어집니다. 이 중 i (1 ≤ i ≤ k)번째 정수 pi는 i번 말이 위치한 칸의 번호를 나타냅니다.
- 2 ≤ n ≤ 109
- 1 ≤ k ≤ min(105, n)
- 1 ≤ d ≤ n - 1
- 1 ≤ p1 < p2 < ... < pk - 1 < pk ≤ n
출력
승현이가 d개의 칸막이들을 잘 설치하여 보존할 수 있는 격자의 수의 최댓값을 출력합니다.
풀이
칸막이를 적절히 배치해서 최대 격자의 수를 구해야 한다.
말과 말 사이는 우리가 보존할 수 있는 공간이다. 그래서 이 공간이 넓은 순으로 보존할 수 있게 칸막이를 배치하는 것이 풀이의 핵심이다.
그런데 만약 말이 1번에 존재하지 않는다면 1부터 다음 말까지의 공간은 칸막이 하나로 보존할 수 있다. 같은 논리로 말이 n번에 존재하지 않는다면 마지막 말부터 n까지의 공간도 칸막이 하나로 보존할 수 있다.
그리고 나머지는 칸막이 2개로 공간을 보존할 수 있다.
이는 직접 그려보면 쉽게 이해할 수 있다.
칸막이 하나로 막을 수 있는 공간은 최대 2개인데 이 공간이 하나이거나 없다면 처리는 간단하다.
-
d가 짝수인 경우는 1 ~ d/2까지 돌면서 공간이 큰 순으로 포함시키면 되고,
-
d가 홀수인 경우는 1 ~ d/2까지 돌면서 공간이 큰 순으로 포함시키고, 하나로 막을 수 있는 공간을 포함하면 된다. (칸막이가 하나 남기 때문에)
조금 까다로운 경우는 칸막이 하나로 막을 수 있는 공간이 2개일 때다
-
d가 짝수인 경우는 하나로 막을 수 있는 공간 2개를 합쳐서 1 ~ d/2까지 돌며 공간이 큰 순으로 포함시키면 된다.
-
d가 홀수인 경우는 짝수인 경우에서 구한 값과 하나로 막을 수 있는 공간 중 큰 값을 포함하고, 1 ~ d/2까지 돌면서 두 개로 막을 수 있는 공간 중 큰 순으로 포함한 값과 비교해서 더 큰 값을 출력해 주면 된다.
2번 째 경우에서 비교해 줘야 하는 이유는 짝수인 경우처럼 계산했을 때 칸막이 하나가 남지만 하나로 막을 수 있는 두 공간의 합이 칸막이 하나를 더 사용했을 때 보다 클 수 있다.
예를 들어
하나로 막을 수 있는 공간이 51, 50이고,
두개로 막을 수 있는 공간이 5 4 3이며,
칸막이가 7개 일 때
51 + 50, 5, 4를 보존하기 위해서 칸막이 6개가 사용되고 총 공간은 110이다.
칸막이를 전부 사용한다면 5, 4, 3, 51이 되는데 이 때 공간은 63이 된다.
그래서 이는 비교해 봐야 알 수 있는 부분이기 때문에 비교 후에 최적 값을 출력하면 된다.
그리디 + 정렬 풀이의 시간 복잡도는 O(k * logk)다.
소스 코드
import java.io.*;
import java.util.*;
public class Main {
static int n, k, d;
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());
k = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
StringTokenizer st2 = new StringTokenizer(br.readLine());
int before = 1;
ArrayList < Integer > one = new ArrayList < > ();
ArrayList < Integer > two = new ArrayList < > ();
for (int i = 0; i < k; i++) {
int h = Integer.parseInt(st2.nextToken());
if (before == 1 && h != 1) {
one.add(h - before);
} else {
if (h - before != 0) {
two.add(h - before);
}
}
before = h + 1;
}
if (before <= n) {
one.add(n + 1 - before);
}
long answer = 0;
if (one.size() == 2) {
ArrayList<Integer> newTwo = new ArrayList<>();
newTwo.add(one.get(0) + one.get(1));
for(int i=0; i<two.size(); i++) {
newTwo.add(two.get(i));
}
Collections.sort(newTwo, Collections.reverseOrder());
for(int i=1; i<=d/2; i++) {
if(i - 1 >= newTwo.size()) {
break;
}
answer += newTwo.get(i-1);
}
long answer2 = Math.max(one.get(0), one.get(1));
if(d % 2 == 1) {
Collections.sort(two, Collections.reverseOrder());
for(int i=1; i<=d/2; i++) {
if(i - 1 >= two.size()) {
break;
}
answer2 += two.get(i - 1);
}
answer = Math.max(answer, answer2);
}
} else {
if (d % 2 == 0) {
if (!one.isEmpty()) {
two.add(one.get(0));
}
} else {
if(!one.isEmpty()) {
answer = one.get(0);
}
}
Collections.sort(two, Collections.reverseOrder());
for (int i = 1; i <= d / 2; i++) {
if (i - 1 >= two.size()) {
break;
}
answer += two.get(i - 1);
}
}
System.out.println(answer);
}
}