[백준 1911번] 흙길 보수하기 (Python)

 

> 파이썬, 그리디 알고리즘, 정렬, 스위핑

 

 

 

 

 

📖 문제 : 흙길 보수하기 (Python)

 

 

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N(1 ≤ N ≤ 10,000)개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이가 L(1 ≤ L ≤ 1,000,000)인 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

 

입력

첫째 줄에 두 정수 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0 이상 1,000,000,000 이하의 정수이다. 입력으로 주어지는 웅덩이는 겹치지 않는다.

 

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

 

예제 입력 1 

3 3
1 6
13 17
8 12

 

예제 출력 1 

5

 

힌트

아래와 같이 5개의 널빤지가 필요하다.

111222..333444555.... // 길이 3인 널빤지
.MMMMM..MMMM.MMMM.... // 웅덩이
012345678901234567890 // 좌표

 

 

 

내 코드

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

puddle = []
for _ in range(N):
    s, e = map(int, input().split())
    puddle.append((s, e))

puddle.sort()

point = 0       # 널빤지로 웅덩이를 가리고 나서, 그 널빤지의 가장 끝 지점을 저장할 변수 -> 그 다음 웅덩이를 가릴 수도 있기 때문에
result = 0

for i in range(N):
    s, e = puddle[i][0], puddle[i][1]

    if point > s:  # 전에 걸친 널빤지가 다음 웅덩이의 일부분을 덮을 경우
        s = point

    cnt = (e - s) // L

    if (e - s) % L != 0:    # 널빤지를 걸쳤는데, 아직 웅덩이가 덜 가려졌을 경우 그 남은 웅덩이는 널빤지 하나 길이보단 짧다.
        cnt += 1
        point = s + L * cnt
    else:
        point = e

    result += cnt

print(result)

 

 

 

Point ! ⭐️ 

• 이 코드는 주석을 보면 이해 하실 수 있을 것이라고 생각합니다 !

 

 

 

 

 

 

백준

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

1911번: 흙길 보수하기