|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
# https://www.acmicpc.net/problem/1449
N, L = map(int, input().split())
hole = list(map(int, input().split()))
# 4 2
# 1 2 100 101
hole.sort()
result = 0
taping = 0
for i in hole:
if taping < i:
taping = i + L - 1
result+=1
print(result)
|
cs |
긴 수도 파이프에서 구멍난 위치(hole) 를 순회하면서, 구멍난 곳에 테이프를 붙인다. 구멍난 위치에 테이프를 붙이면 구멍난 위치 + 테이프의 길이 -1 만큼 테이프가 붙는다.
예를들어, hole = [1, 2, 100, 101] 일 때,
위치 1에 길이 2인 테이프를 붙이면 1(구멍난위치) + 2(테이프의길이) - 1 의 위치까지 테이프가 붙여진다는 것이다.
즉, 위치 1에 길이 2인 테이프를 붙이면 2까지 테이프가 붙는다. 길이가 2인 테이프를 위치 1에 붙였으니 1과 2에 테이프가 붙은것이다.
어디까지 테이프가 붙었는지 taping 에 저장하고, 구멍난 위치가 taping 보다 크다면 테이프가 붙여지지 않은 구멍이라는 소리므로
테이프를 붙여주고, taping 에 어느 위치까지 테이프가 붙었는지 저장해준 후, 결과에 1을 추가한다.
구멍난 위치가 taping 보다 작거나 같다면 그 위치는 이미 테이프가 붙어있는 곳이므로 무시한다.
### 내가 직접 한번에 이렇게 깔끔하게 풀었으면 좋았겠지만 안타깝게도 나는 이런 그리디스러운 사고를 하지 못했다. 연습이 더 필요한듯..
어제 잠을 잘 못자서 그런지 머리가 안돌아간다.이상하게 알고리즘 공부한후부터 새벽 4시쯤 말똥말똥하게 잠에서 깬다.
예전에 회사 업무로 과도한 스트레스를 받았을때 동일한 경험을 한 적이 있는데, 알고리즘 공부가 나름 스트레스를 주나보다.