[Baekjoon 1911 / Python / 골드5] 흙길 보수하기

문제

import sys

input = sys.stdin.readline

# N개의 웅덩이, L길이의 널빤지

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

water = []

# 겹치는 웅덩이는 들어오지 않는다

# 웅덩이 좌표 : [1, 6] -> 1 2 3 4 5

for _ in range(N):

    water.append(list(map(int, input().split())))

sortedWater = sorted(water, key=lambda x: (x[0])) # 시작 위치 기준으로 정렬

def fix(size, L):

    if size % L >= 1:

        return size // L + 1

    else:

        return size // L

def solve():

    result = 0

    finalFix = -1

    # 웅덩이가 1개뿐일 경우

    if N == 1:

        size = sortedWater[0][1] - sortedWater[0][0]

        return fix(size, L)

    # 웅덩이가 여러개일 경우

    for i in range(N):

        size = sortedWater[i][1] - sortedWater[i][0] # 웅덩이 크기

       

        if size < 0: # 웅덩이 크기가 음수일 경우

            try:

                if finalFix >= sortedWater[i+1][0]: # 덮인 부분이 다음 웅덩이에 겹쳤다면 다음 웅덩이 시작 지점 미루기

                    sortedWater[i+1][0] = finalFix + 1

            except:

                # 마지막 웅덩이일 경우

                continue

            continue

        fixResult = fix(size, L)

        result += fixResult

        finalFix = sortedWater[i][0] + (L * fixResult) - 1 # 마지막으로 널빤지 덮인 위치(인덱스)

        try:

            if finalFix >= sortedWater[i+1][0]: # 덮인 부분이 다음 웅덩이에 겹쳤다면 다음 웅덩이 시작 지점 미루기

                sortedWater[i+1][0] = finalFix + 1

        except:

            # 마지막 웅덩이일 경우

            continue

   

    return result

print(solve())

 

그리디 문제이다. 웅덩이의 위치가 좌표로 제공되며, L 길이의 널빤지를 최소 몇 개를 사용해야 웅덩이를 전부 덮을 수 있는지 계산해야 한다.

 

먼저 웅덩이를 입력받은 후 시작지점 기준으로 정렬해준다. 겹치는 웅덩이는 제공되지 않는다.

필요한 널빤지 개수는 "웅덩이 크기 // L(널빤지길이)" 로 계산한다. 이때 나머지가 존재한다면 널빤지 1개를 추가한다.

 

이 문제에서 가장 중요한 부분은, 앞서 덮은 널빤지가 뒤쪽 웅덩이까지 덮었을 때에 대한 예외처리이다.

따라서 최종적으로 덮인 부분(인덱스)을 항상 계산해두고, 다음 웅덩이 시작지점과 겹칠 경우 시작지점을 옮겨줘야 한다.

이렇게 할 경우 다음 웅덩이를 덮을 필요가 없는 경우(웅덩이 크기가 음수일 경우)가 생긴다. 그러면 다시 한번 다음 웅덩이와 최종 덮인 부분이 겹쳤는지 확인해 주고 continue로 넘어가면 된다.

 

try except 부분은 대단한 건 아니고 현재 코드에서는 널빤지가 다음 시작지점과 겹치는지 확인하는 부분에서, 마지막 웅덩이일 경우 "i+1" 부분 때문에 index out of range 가 뜨기 때문에 마지막 웅덩이로 판단하고 continue 해주는 것이다.

 

그냥 if문으로 걸어도 상관은 없는데 매번 조건검사를 해야 하니까 연산횟수 측면에서 try가 나을거라 생각해서 이렇게 해 봤다.