[BOJ] 1911 흙길 보수하기 Python

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

1911번: 흙길 보수하기

흙길 보수하기 

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

5162

1911

1459

37.382%

문제

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

입력

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

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

출력

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

예제 입력 1 복사

3 3
1 6
13 17
8 12

예제 출력 1 복사

5

 

풀이 코드 (정답 참고)

import sys
input = sys.stdin.readline

n, l = map(int, input().split())
holes = []
for _ in range(n):
    holes.append(list(map(int, input().split())))
holes.sort(key=lambda holes: holes[0])

cur = 0
cnt = 0
for start, end in holes:
    if cur > start:
        start = cur
    while start < end:
        start += l
        cnt += 1
    cur = start
print(cnt)

 

처음 풀었을 때 메모리 초과가 나서 다른사람 코드를 참고했다.

여기서 핵심은 "A라는 웅덩이를 메꾸기 위해 널판지를 깔았을 때 그 다음 B웅덩이의 일부분도 커버하는 경우" -> 이 부분을 잘 처리해주면 된다. -> 이 부분을 어떻게 해줘야 할지 몰라서 메모리 초과가 났다.

 

그리고 널판지를 깔 때 궅이 리스트를 따로 안 만들고 start, end 값만 가지고 계산해주면 된다.

문제를 풀 때 어떻게 푸는게 더 효율적인지, 정말 필요한 자료형인지 고민해보고 풀어야 한다.