[그리디] 백준_흙길 보수하기

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

입력 예

3 3
1 6
13 17
8 12

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

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

1911번: 흙길 보수하기

---

시간 초과 코드

import sys
input = sys.stdin.readline

n,l=map(int,input().split())
ungdung=[]
for i in range(n):
  ungdung.append(list(map(int, input().split())))

#아이디어:웅덩이 시작 좌표에 맞춰서 널빤지를 깐다. 만약, 겹친다면 이어서 붙이기

#시작좌표를 알기 위해 정렬하기
ungdung.sort(key=lambda x:x[0])

cnt=0
pre_end=0

for start, end in ungdung: 
  if start>end:
    continue
    
  #이전 널빤지가 현재 웅덩이를 덮고 있는 경우
  if pre_end>start:#이전 널빤지가 현재 웅덩이에 걸쳐 있음
    start=pre_end#이전 널빤지의 끝위치부터 시작
    
  #널빤지 깔기
  while start<end:
    start+=l
    cnt+=1 #널빤지 깔기
    
  pre_end=start #다음 반복문에서 이전 널빤지의 끝 위치는 while문에서 최종적으로 널빤지를 깔고 나온 위치를 담고 있는 start임
  
print(cnt)

웅덩이의 시작부터 끝까지 가능한만큼 널빤지를 하나씩 까는 코드입니다. 
이중 반복문으로 인해 시간초과가 발생했습니다.

맞은 코드

import sys
input = sys.stdin.readline

n,l=map(int,input().split())
ungdung=[]
for i in range(n):
  ungdung.append(list(map(int, input().split())))

#아이디어:웅덩이 시작 좌표에 맞춰서 널빤지를 깐다. 만약, 겹친다면 이어서 붙이기

#시작좌표를 알기 위해 정렬하기
ungdung.sort(key=lambda x:x[0])

cnt=0
pre_end=0 #널빤지를 붙이고 난 끝 부분 좌표
total_cnt=0

for start, end in ungdung: 
  if pre_end>end: #이전 널빤지가 현재 웅덩이를 모두 덮고 있는 경우
    continue

  #이전 널빤지가 현재 웅덩이를 전혀 덮지 않는 경우
  if pre_end<start:
    pre_end=start#현재 웅덩이의 시작위치부터 덮으면 됨

  start_to_end = end-pre_end #널빤지를 깔 처음부터 end까지의 길이

  #start_to_end까지 깔 수 있는 널빤지 개수세기
  cnt = (start_to_end+l-1)//l #그림 추가설명

  #널빤지를 깐 최종 위치 계산
  pre_end+=cnt*l

  #최종 널빤지 개수 계산
  total_cnt+=cnt

print(total_cnt)

이중 for문을 사용하지 않고 널빤지의 개수를 계산하는 방법입니다.

이를 위해 cnt = (start_to_end+l-1)//l 코드가 필요합니다.

아래는 이 공식에 대한 설명입니다. 참고한 블로그 https://zrr.kr/mVW5

이 공식을 통해 시간 초과 없이 구현해낼 수 있습니다!

이외의 코드 설명은 주석에 자세히 달아두었으니 참고 부탁드립니다.

파닭파닭 문제를 푸면서 나머지 연산의 무서움을 느꼈기 때문에 이 문제도 최대한 나머지 연산을 쓰지 않고 구현하려고 하다보니 이중 반복문을 써서 시간 초과가 났다.

나누는 수(제수)를 더해주고 나누어 떨어지는 걸 방지하기 위해 1을 빼는 방법을 알게 되어 알찬 코드 풀이였던 거 같다. 

3일 전에 못 풀었던 문제를 다시 풀어봐서 좋았다!