Sign in Subscribe
PS

[PS] BOJ 1911 / 흙길 보수하기

Minjun Kim

• 5 min read
[PS] BOJ 1911 / 흙길 보수하기
문제 링크: https://www.acmicpc.net/problem/1911
Thumbnail: Photo by Duc Van (Unsplash)

스위핑 문제입니다. 널빤지 배치를 효율적으로 하는 과정에 대해 조금 고민했습니다.

풀이

스위핑

특정 범위에 대한 입력을 정렬한 뒤, 순차적으로 읽어나가는 기법입니다.

ponds = []

for _ in range(N):
    s, e = map(int, input().strip().split())
    ponds.append((s, e))

ponds.sort(key=lambda p: p[0])

스위핑

널빤지 배치하기

널빤지를 배치할 수 있는 경우의 수를 생각해 보자.

  1. 이전에 배치된 널빤지에 완전히 덮일 때 (배치할 필요 X)
  2. 이전에 배치된 널빤지와 일부 겹칠 때 (나머지 부분만 배치)
  3. 이전에 배치된 널빤지와 겹치는 부분이 없을 때 (신규 배치)

이 과정을 반복문을 통해 각 물웅덩이에 대해 진행한다.

last_covered = -1    # 이전에 배치된 널빤지의 가장 끝 좌표
pond_idx = 0         # 현재 물웅덩이 정보의 인덱스
cnt = 0              # 필요한 총 널빤지 개수

# 널빤지가 수의 최대 범위를 넘지 않고, 물웅덩이를 모두 덮을 때까지 계속 반복
while last_covered <= 1_000_000_000 and pond_idx < N:
    s, e = ponds[pond_idx]  # s는 물웅덩이의 시작 좌표, e는 끝 좌표.
    ... (아래 과정을 진행)

(1) 이전에 배치된 널빤지에 완전히 덮일 때

새 널빤지를 덮을 필요가 없는 경우이다. 바로 다음 반복으로 넘어가면 된다.

if last_covered >= e:   # 이미 이번 물웅덩이까지 덮인 경우.
    pond_idx += 1
    continue

A == B 일 때 예외 처리

(2) 이전에 배치된 널빤지와 일부 겹칠 때

last_covered 변수에 저장된 이전에 배치된 널빤지의 끝 좌표를 사용해, 아직 덮어지지 않은 부분만 계산해 덮어준다.

먼저, 덮어야 하는 남은 부분을 계산해 needed에 저장하고, 이후 필요한 최소 널빤지 개수를 계산해 c에 저장한다.

마지막으로, last_covered를 이번에 덮어진 널빤지의 끝 좌표로 계산해서 저장한다.

elif last_covered >= s:     # 이미 일부가 덮여 있고, 나머지 부분을 덮는 상황.
    needed = e - last_covered
    c = needed // L
    if needed % L > 0:
        c += 1
    last_covered = last_covered + c * L
    pond_idx += 1
    cnt += c

결과 출력

(3) 이전에 배치된 널빤지와 겹치는 부분이 없을 때

덮어야 하는 길이를 needed에 계산해 저장하고, 필요한 최소 널빤지의 개수를 계산해 c에 저장한다. 이후, 총 널빤지의 길이를 require에 저장한다.

이제 널빤지를 배치할 수 있는 경우를 3가지로 나눈다.

  1. 다음 물웅덩이와 겹치게 덮을 수 있다면
    1. 다음 물웅덩이의 시작 좌표보다 (현재 물웅덩이의 시작 좌표 + 널빤지 길이)가 더 큰지 비교해 확인할 수 있다.
    2. 최대한 다음 물웅덩이쪽으로 널빤지를 배치하고, last_covered 변수를 그에 맞게 갱신한다.
  2. 현재 물웅덩이의 시작 좌표보다 더 작은 쪽으로만 튀어나오게 널빤지를 배치할 수 있다면
    1. (현재 물웅덩이의 끝 좌표 - 널빤지 길이) 가 이전에 배치된 널빤지의 끝 좌표 last_covered보다 더 큰지 비교해 확인할 수 있다.
    2. 이 경우, last_covered는 현재 물웅덩이의 끝 좌표가 된다.
  3. 그 이외의 경우
    1. 앞선 두가지 이외의 모든 경우는 last_covered 에서부터 바로 널빤지를 이어서 배치해도 물웅덩이를 보두 덮을 수 있음이 보장된다.
    2. 따라서, last_covered는 이전 last_covered에 현재 널빤지의 총 길이 required를 더한 값으로 갱신된다.
else:   # 아예 새로 덮는 상황.
    needed = e - s
    c = needed // L
    if needed % L > 0:
        c += 1
    require = c * L
    # 다음번 물웅덩이 범위 고려해서 이번 널빤지가 겹치게 할 수 있다면 그쪽으로 빼고, 아니라면 그냥 왼쪽으로 뺀다.
    if pond_idx < N - 1 and (s + require) >= ponds[pond_idx + 1][0]:
        last_covered = s + require
    elif (e - require) > last_covered:  # 이전 범위로만 튀어나오게 널빤지를 덮을 수 있다.
        last_covered = e
    else:
        last_covered += require
    pond_idx += 1
    cnt += c

결과 출력

전체 코드

input = open(0).readline
N, L = map(int, input().strip().split())

ponds = []

for _ in range(N):
    s, e = map(int, input().strip().split())
    ponds.append((s, e))

ponds.sort(key=lambda p: p[0])

last_covered = -1
pond_idx = 0
cnt = 0
while last_covered <= 1_000_000_000 and pond_idx < N:
    s, e = ponds[pond_idx]
    if last_covered >= e:   # 이미 이번 물웅덩이까지 덮인 경우.
        pond_idx += 1
        continue

    elif last_covered >= s:     # 이미 일부가 덮여 있고, 나머지 부분을 덮는 상황.
        needed = e - last_covered
        c = needed // L
        if needed % L > 0:
            c += 1
        last_covered = last_covered + c * L
    
    else:   # 아예 새로 덮는 상황.
        needed = e - s
        c = needed // L
        if needed % L > 0:
            c += 1
        require = c * L
        # 다음번 물웅덩이 범위 고려해서 이번 널빤지가 겹치게 할 수 있다면 그쪽으로 빼고, 아니라면 그냥 왼쪽으로 뺀다.
        if pond_idx < N - 1 and (s + require) >= ponds[pond_idx + 1][0]:
            last_covered = s + require
        elif (e - require) > last_covered:  # 이전 범위로만 튀어나오게 널빤지를 덮을 수 있다.
            last_covered = e
        else:
            last_covered += require
    pond_idx += 1
    cnt += c
print(cnt)

solution.py