[BOJ] 1911 - 흙길 보수하기

문제 출처

백준 1911 - 흙길 보수하기

 

풀이

입력된 웅덩이를 정렬한 뒤 웅덩이들의 목록을 처음부터 한번 돌아주는 스위핑 알고리즘을 이용해 필요한 널빤지 수를 구해주었습니다.

 

스위핑을 통해 다음과 같은 과정을 반복했습니다.

 

1. 널빤지를 놓을 시작 점을 잡아주었습니다.

2. 웅덩이의 시작이 널빤지를 놓을 시작 점보다 더 멀리있다면 시작 점을 갱신해주었습니다.

3. 하나의 웅덩이가 끝나는 부분에서 시작 점을 빼주어 필요한 널빤지의 갯수를 구해주었습니다.

4. 널빤지를 놓은 만큼 시작 점을 뒤로 갱신해주었습니다.  

 

중요한 점은 널빤지가 여러 웅덩이에 걸쳐있을 수 있다는 점입니다. 따라서 가장 마지막으로 놓은 널빤지가 끝나는 부분으로 시작 점을 잡아 최소의 널빤지를 사용할 수 있게 했습니다.

 

코드

small-j/Algorithm