• 물이 새는 곳의 범위가 (n - 0.5) ~ (n + 0.5) 이고, N의 최대 크기가 1000이기 때문에 2배로 늘려줬다.
  • 2000 크기의 배열을 두고, 물이 새는 위치를 1, 테이프로 막은 위치를 2로 설정
  • 물이 새는 시작 위치부터 테이프 길이만큼 막아주면 그게 매 순간 최적의 해이다.
    • 따라서, greedy로 구현하였다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41



#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>

using namespace std;

#define HOLE 1
#define TAPE 2

int N, L;
int arr[2002];

int solution() {
	int cnt = 0;
	for (int i = 1; i <= 2000; i++) {
		if (arr[i] != HOLE) continue;

		cnt++;
		int j = i;
		for (; j <= 2000 && j <= i + L; j++)
			arr[i] = TAPE;
		i = j-1;
	}
	return cnt;
}

int main() {
	scanf("%d%d", &N, &L);
	L *= 2;
	for (int i = 0; i < N; i++) {
		int tmp;
		scanf("%d", &tmp);
		tmp *= 2;
		arr[tmp-1] = 1;
		arr[tmp] = 1;
		arr[tmp+1] = 1;
	}
	printf("%d", solution());
}