[백준] 1911번 : 흙길 보수하기

1911번: 흙길 보수하기

1911번: 흙길 보수하기

🤔 문제분석

오름차순으로 정렬한뒤, 위치를 가르키는 임의의 변수를 활용하여 문제를 해결하였습니다. 여기서 포인트는 임의의 위치의 변수를 start가 더 클경우 pos를 start로 초기화 시켜줍니다. pos가 end에 도달 할때까지 개수를 증가시키며 pos에 L을 더합니다.

💻 코드

import sys
input = sys.stdin.readline

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

water = []
for _ in range(N):
    water.append(tuple(map(int, input().split())))

water.sort()

pos = 0
cnt = 0
for start, end in water:
    if start > pos:
        pos = start
    
    while end > pos:
        pos += L
        cnt += 1

print(cnt)

🎯 피드백 및 개선사항

수학적인 개념을 활용하여 시간복잡도를 줄일 수 있습니다. 나머지 연산을 활용하여 L로 얼마나 나눌 수 있는지 개수를 카운팅하고 나머지가 1보다 크다면 하나더 증가시켜 주어야합니다.

from sys import stdin
input = stdin.readline
n, l = map(int, input().split())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))
p.sort(key=lambda x: x[0])
last = p[0][0]
cnt = 0
for i in range(n):
    if last < p[i][0]:
        last = p[i][0]
    ccnt = (p[i][1] - last) // l
    if (p[i][1] - last) % l != 0:
        ccnt += 1
    # print(p[i][0], p[i][1], last, ccnt, cnt)
    last += ccnt * l
    cnt += ccnt
    
print(cnt)