[BOJ] 1191 흙길 보수하기

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

비가 많이 와서 물 웅덩이 생겼는데 길이 l짜리 널빤지 최소로 써서 덮을 때 그 개수를 구하는 문제이다.

예전에 선 긋기 문제에서 사용했던 코드를 참고해서 풀었다.

코드 1 - 시간초과

n, l = map(int, input().split())

need = [list(map(int, input().split())) for _ in range(n)]

need.sort()

left = need[0][0]
right = left + l - 1

ans = 1

for i in range(0, n):
  need[i][1] -= 1
  if right > need[i][1]:
    continue
  elif need[i][0] <= right < need[i][1]:
    while right < need[i][1]:
      right += l
      ans += 1
  elif right < need[i][0]:
    left = need[i][0]
    right = left + l - 1
    ans += 1
    while right < need[i][1]:
      right += l
      ans += 1
    
  
print(ans)

웅덩이의 끝이라고 표현된 숫자가 웅덩이가 끝나고 땅이 시작되는 지점을 가리키기에 for문 돌면서 끝을 1씩 줄여주었다.

그리고 첫번째 웅덩이 시작부분에 널빤지를 일단 두고 시작했다.
각 웅덩이를 돌면서 웅덩이의 시작점이 널빤지의 오른쪽 끝보다 뒤에 있고, 널빤지의 끝이 웅덩이의 끝보다 작으면 웅덩이 전부 덮을 때까지 널빤지를 추가했다.

만약 널빤지의 오른쪽 끝이 새로운 웅덩이보다 앞에 있으면 새롭게 시작했고, 거기서 해당 웅덩이를 전부 덮을 때까지 널빤지를 추가해줬다.

만약 웅덩이가 널빤지에 이미 덮인 상태라면 continue로 지나갔다.

근데 이렇게 했는데 시간초과로 실패했다. 널빤지를 추가하는 while문이 문제인 것 같다. 수학연산으로 해결할 필요가 있어 보인다.

코드 2

n, l = map(int, input().split())

need = [list(map(int, input().split())) for _ in range(n)]

need.sort()

left = need[0][0]
right = left + l - 1

ans = 1

for i in range(0, n):
  need[i][1] -= 1
  if right > need[i][1]:
    continue
  elif need[i][0] <= right < need[i][1]:
    dif = need[i][1] - right
    plates = dif // l + (1 if dif % l else 0)
    
    right += plates * l
    ans += plates
    
    
  elif right < need[i][0]:
    left = need[i][0]
    right = left + l - 1
    ans += 1
    if right < need[i][1]:
      dif = need[i][1] - right
      plates = dif // l + (1 if dif % l else 0)
    
      right += plates * l
      ans += plates
    
  
print(ans)

단순히 더해주던 while문을 수학 계산으로 처리했다.
웅덩이의 오른쪽 끝과 right의 차이를 구한 후 몫과 나머지 유무를 통해 웅덩이를 전부 덮기 위해 필요한 널빤지의 개수를 구했다.
그리고 그만큼 right와 plates에 더해주는 방식으로 바꾸었더니 통과할 수 있었다.

단순 더하기용 while은 최초 코드 만들 때는 그렇게 하더라도 짜고 나서 다시 생각해볼 필요가 있겠다.