[python] 백준 1191번 : 흙길 보수하기

https://www.acmicpc.net/problem/1911

1911번: 흙길 보수하기

 

문제를 풀기 위한 아이디어는 '어느 위치에서 탐욕적으로 널빤지로 웅덩이를 덮을 수 있는가'이다. 자세히 말하자면 한 웅덩이를 덮고서 다음 웅덩이에 널빤지가 걸치는 경우, 이 부분을 제외하고 웅덩이를 덮어주자는 것이다. 해당 아이디어를 가지고 코드로 구현하면 아래와 같다. 

 

1. 코드 구현

import sys
input = sys.stdin.readline
n, L = map(int, input().split())
pools = [list(map(int, input().split())) for _ in range(n)]
# 웅덩이 좌표 오름차순 정렬
pools.sort(key=lambda x:x[0])

# 웅덩이를 덮은 마지막 널빤지의 위치 
cur = 0
# 널빤지의 개수 
cnt = 0
for start, end in pools:
    if start > end:
        continue
    # 이전 웅덩이에서 덮은 널빤지가 해당 웅덩이를 덮고있는 경우 
    if cur > start:
        start = cur
    # 널빤지의 개수 카운트 
    while start < end:
        start += L
        cnt += 1
    cur = start

print(cnt)

 

 

 

2. 코드 구현 

import sys
input = sys.stdin.readline
N, L = map(int, input().split())
# 입력과 동시에 좌표 오름차순 정렬
pools= sorted(tuple(map(int, input().split())) for i in range(N))

# 널빤지의 개수, 웅덩이를 덮은 널빤지의 마지막 위치 
res, s = 0, 0
for start, end in pools:
  s = max(start, s)
  diff = end - s
  count = (diff + L - 1) // L
  res += count
  s += count * L

print(res)

위 코드를 숏코딩하면 아래와 같이 구현할 수 있다. while 문을 사용하지 않고 count의 개수를 구해주었는데 설명을 위해 아래 사진을 참고하길 바란다. 

예를 들어, 웅덩이의 시작 위치는 start = 0, 마지막 위치는 end = 8 이라고 하자. 그리고 널빤지의 길이 L이 3이라면 다음과 같이 diff//L =  2 가 된다. 하지만 우리는 나머지 부분마저 널빤지로 덮기를 원한다. 따라서 나머지 부분도 카운팅 해주기 위해 L 값을 간격 diff에 더해 길이를 보정시켜 줄 수 있다. 

그렇다면 왜 -1을 해주는 것일까? 그 이유는 diff 값이 L의 배수일 경우 문제가 되기 때문이다. 

예를 들어 간격 diff가 6이고 L=3이라면 카운트 값이 2가 되어야 하는데 (diff + L)//3 = 9가 된다. 따라서 이를 막기 위해 -1을 빼주면 모든 경우에 대해서 널빤지의 개수에 대해 카운팅이 가능하다.