백준 1911. 흙길 보수하기

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

1911번: 흙길 보수하기

 

웅덩이 시작 기준 오름차순 정렬, 시작 같다면 끝 기준 오름차순 정렬 해준다.

 

last 가 마지막에 놓은 널빤지의 끝지점 이라고 하면 

어떤 웅덩이 하나를 덮기 위해 놓아야할 널빤지의 위치는 max(last, 웅덩이 시작지점) 이다. 

그러면 해당 웅덩이를 모두 덮기 위해 필요한 널빤지의 길이는 : 웅덩이의 끝지점 r - max(last, 웅덩이 시작지점) 이 된다.

이때 이 값은 음수가 될수 있다.

 

예를들어 입력이 다음과 같을때를 생각해보자.

3 3

1 5

3 7

4 6 

 

1,5 웅덩이를 길이 3의 널빤지 두개로 덮고나면 last=7이된다.

3,7 도 이때 같이 커버된다.

4,6 을 생각해보면 max(last,웅덩이 시작지점) = 7 이된다.

웅덩이의 끝지점 r - max(last, 웅덩이 시작지점) = 6 - 7 = -1 이된다.

따라서 음수가 되면 0으로 보정해줘야 한다.