[백준/파이썬] 1911 흙길 보수하기

이 문제는 라인스위핑 문제이다.
https://www.acmicpc.net/problem/1911

라인 스위핑은 쉽지만 자칫 잘못하면 수렁에 빠질 수 있다. 경우의 수를 잘 판단하고 접근해야 한다.

라인스위핑에서는 시작점(s), 종점(e)을 기록하는게 가장 중요하다.
그리고 나서 어떤 경우가 발생하는지 생각해보자.

먼저, 라인스위핑에서는 기본적으로 input 을 정렬해준다.
arr = [[*map(int, input().split())] for _ in range(N)]
그리고 난 후 for 문을 순회한다.

두 가지 경우는 다음고 같다.
1. 널빤지를 연결해서 붙일 수 없을 정도로 물 웅덩이가 멀리 떨어진 경우.
이 경우에는 시작점(s)를 다시 설정해주어야 한다.

2. 널빤지를 연결해서 붙여두었더니 다음 물 웅덩이가 그 범위 안에 들어와있는 경우 -> 이 경우는 시작점(s)을 다시 설정할 필요가 없다.

두 가지 경우만이 모든 경우를 커버하는데, 시작점을 이동해야 하는 가장 중요한 이유는 널빤지의 위치를 낭비하지 않고 필요한 부분만 덮음으로써 최소로 웅덩이를 덮을 수 있기 때문이다.
s는 이동하는 점이다. 아울러서 e 점 역시 이동하는데, 웅덩이의 가장 끝 점보다 더멀리 가면 된다 (while문을 쓰는 이유)

아래 코드가 정답이지만, pypy3에서만 돌아간다는 점에 유의하자. 속도가 좀 더 느린 python3로 정답을 통과하려면 while문 대신 산수를 이용한 개선된 코드를 사용하는게 좋다.

pypy3에서만 통과하는 정답 코드

N, L =  map(int, input().split())
arr = [[*map(int, input().split())] for _ in range(N)]
arr.sort(key = lambda x: x[0]) # 먼저 웅덩이 시작점을 기준으로 한다.
s,e, cnt = 0,0,0
for elem in arr:
    if e < elem[0]:
        s = elem[0]
        e = s
        while e < elem[1]:
            cnt += 1
            e += L
    elif s <= elem[0] <= e:
        while e < elem[1]:
            cnt += 1
            e += L
print(cnt)

산수를 이용한 개선된 코드 (while 문 대신)

N, L =  map(int, input().split())
arr = [[*map(int, input().split())] for _ in range(N)]
arr.sort(key = lambda x: x[0]) # 먼저 웅덩이 시작점을 기준으로 한다.
s,e, cnt = 0,0,0
for elem in arr:
    if e < elem[0]:
        s = elem[0]
        e = s
        if not (elem[1] - s) % L:
            cnt += (elem[1] - s) // L
            e = elem[1]
        else:
            cnt += (elem[1] - s) // L + 1
            e = elem[1] - (elem[1] - s) % L + L
    elif s <= elem[0] <= e:
        if not (elem[1] - e) % L:
            cnt += (elem[1] - e) // L
            e = elem[1]
        else:
            cnt += (elem[1] - e) // L + 1
            e = elem[1] - (elem[1] - e) % L + L
print(cnt)