[백준] 1449번: 수리공 항승 (sol.7)

풀이시간: 1시간

1. 나의 풀이

import heapq as hq

N, L = map(int, input().split())
holes = []

for hole in map(int, input().split()):
    hq.heappush(holes, hole)

count = 0

index = hq.heappop(holes)

while holes:
    next_hole = hq.heappop(holes)
    if next_hole - index < L:
        continue
    else:
        count += 1
        index = next_hole

count += 1

print(count)

• 구멍은 순서대로 있고 어떠한 구간 내에서 최소 갯수로 묶어서 구멍을 막을 수 있는 경우는 여러가지이나,
  경우의 수는 동일함으로 greedy로 접근
• 배열로 구멍리스트를 받을 경우 정렬을 고려했을 때 시간초과가 날 것 같아 힙으로 구현
• 테이프 사용시 구멍 양옆으로 0.5씩 간격을 두는 데, 이어서 붙이는 경우도 첫번째 구멍 앞과 마지막 구멍 뒤만
  신경쓰면 되므로 구멍 구간 길이의 +1씩만큼의 길이의 테이프 하나가 필요하다고 파악
• 기준이 되는 구멍을 설정하고 테이프를 이어붙이다가 테이프의 길이가 모자르면 테이프를 사용한 갯수를 +1하고
  테이프 길이가 짧아 못막은 구멍을 기준으로 설정
• 테이프 길이가 모자를 때까지 구멍을 막다가 더이상 막을 구멍이 없으면 while을 빠져나오므로 while문 밖에서
  사용한 테이프 갯수 +1

2. 또다른 풀이

N, L = map(int, input().split())

coord = [False] * 1001
for i in map(int, input().split()):
	coord[i] = True

ans = 0
x = 0
while x < 1001:
	if coord[x]:
		ans += 1
        x += L
    else:
    	x += 1

print(ans)

• 물이 새는 곳이 1000보다 작거나 같은 자연수 조건이므로 구멍을 좌표로 구현
• x는 좌표상 구멍을 체크하는 기준점
• 구멍을 만나면 길이 L만큼의 테이프를 사용하면 사이의 모든 구멍이 막힌다.
• 테이프를 사용 후에는 기준점에서 그 길이만큼 더한 구멍 위치부터 구멍여부를 확인하면 된다. (양옆 0.5씩 여유있게 붙인다.)

3. 보완할 것

• 글로만 이해가 안될 때는 상황을 그림으로 그려보자.
• 상황을 배열 좌표로 구현하는 방법도 고려를 해보자.
• 한 케이스가 완료가 안되었으면 다음 케이스로 넘어갈 때까지 그 한 케이스에 집중한다.
• 예시 입력사항 이외 경계값이나 터무니없는 범위등으로 테스트를 해보자.