[python] 백준 1911 흙길 보수하기

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

1911번: 흙길 보수하기

 

문제 해결

• 웅덩이를 널빤지로 막는 문제
• 문제는 널빤지의 규격이 정해져 있고 웅덩이를 메우고 남는 너비가 다른 웅덩이의 일부 혹은 전체를 막을 수 있다는 것이다.
• 따라서 웅덩이를 원점에서 가장 가까운 것부터 메워가며 널빤지 끝자락을 포인트로 잡을 것이다.
• 널빤지를 효율적으로 사용하기 위해 다음 웅덩이의 일부를 이전 널빤지가 커버했으면 이어서 붙이고 전체를 커버했으면 다음 웅덩이를 커버하면 될 것이다. 독립적(널빤지가 다음 웅덩이에 영향을 안주면)이면  다음 웅덩이 시작점부터 널빤지를 놓으면서 붙이면 된다.

 

CODE

n, l = map(int, input().split()) # 웅덩이 개수, 널빤지 길이
pond = [tuple(map(int, input().split())) for _ in range(n)]
pond.sort(key= lambda x: (x[0],x[1]))
point = pond[0][0] # 널빤지 이어붙이고 끝자락을 변수 point로 둘 것이다. 초기에는 널빤지를 둔 곳이 없으므로 시작해야할 포인트로 변수를 잡는다.
cnt = 0
for start, end in pond:
    if point > end:
        continue
    elif point < start:
        point= start
    dist = end - point
    r = 1
    if dist % l ==0:
        r = 0
    count = dist//l + r
    point += count*l # 시작점에서 널빤지를 이어붙이고 마지막 끝자락
    cnt += count
print(cnt)