[BOJ 백준 알고리즘] 1911번 문제/흙길 보수하기

 

 

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

1911번: 흙길 보수하기

문제

어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 <= N <= 10,000) 개의 물웅덩이가 생겼다. 월드학원은 물웅덩이를 덮을 수 있는 길이 L (L은 양의 정수) 짜리 널빤지들을 충분히 가지고 있어서, 이들로 다리를 만들어 물웅덩이들을 모두 덮으려고 한다. 물웅덩이들의 위치와 크기에 대한 정보가 주어질 때, 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 구하여라.

---

입력

첫째 줄에 N과 L이 들어온다.

둘째 줄부터 N+1번째 줄까지 총 N개의 줄에 각각의 웅덩이들의 정보가 주어진다. 웅덩이의 정보는 웅덩이의 시작 위치와 끝 위치로 이루어진다. 각 위치는 0이상 1,000,000,000이하의 정수이다.

---

출력

첫째 줄에 모든 물웅덩이들을 덮기 위해 필요한 널빤지들의 최소 개수를 출력한다.

---

예제는 생략한다

 

접근방향

그리디 그리디 그리디... 그리디 알고리즘 문제가 약한 거 같아서

백준의 그리디 문제를 모은 문제집에서 조금씩 풀어보고 있다.

전체적으로 그 유형이 다 같은 듯 다른 듯하여 아직은 감을 잡기기 쉽지가 않다.

 

어쨌든 문제 얘기를 하자면 널빤지를 최소한의 개수로 쓰면서 웅덩이를 덮으라고 하였으니 웅덩이의 첫 지점부터 널빤지를 겹치지 않고 차례로 놓으면 되지 않을까? 하는 생각을 하면서 문제를 풀어나갔다.

 

우선 한 웅덩이를 다 덮는데 널빤지가 얼마나 필요할지는 O(1)에 구할 수 있다.

바로 웅덩이의 넓이를 널빤지 하나의 넓이로 나눈 몫이다.

예를 들어 웅덩이의 넓이가 6이고 널빤지 하나의 넓이가 3이면 이 웅덩이를 덮는데 널빤지 2장이 필요하다.

 

간단하다.

 

만약 웅덩이의 넓이가 7이고 널빤지는 마찬가지로 3의 넓이를 갖는다면?

웅덩이를 완전히 다 덮는 데는 3장의 널빤지가 필요하다. 

 

여기서 웅덩이의 넓이를 널빤지 하나의 넓이로 나눴을 때

나머지가 있다면 널빤지가 한 장 더 필요하다는 것을 볼 수 있다.

 

python 코드로 쓰자면 다음과 같다.

 

# width : 웅덩이 넓이, log_num : 널빤지 갯수, l : 널빤지 하나의 넓이
log_num = width // l
if(width % l != 0):
	log_num += 1

 

 

이런 식으로 각 웅덩이마다 필요한 널빤지 개수를 체크해주고 더하면 정답이다~

라고 하면 틀렸습니다. 를 받을 수 있다.

 

우리는 다음과 같은 경우를 체크해야 한다.

만약 널빤지 한 장이 다음 웅덩이의 일부를 덮어버린다면? 아예 전부 덮어버린다면?

그러면 다음 웅덩이에서 널빤지를 추가로 쓸 필요가 없게 된다. 이를 고려해야 한다는 것이다.

 

그래서 포인터 역할을 하는 변수를 하나 선언해서 널빤지를 사용할 필요가 없는 웅덩이를 패스해주면서 널빤지 개수를 더해나가면 되는 것이다. 이 포인터 값을 설정하는 게 문제를 풀 때 조금 헷갈렸다. 이런 건 투포인터 문제를 풀 때도 익숙해져야 하는 건데 생각해보니 나는 투포인터 문제도 잘 못푸는 거 같다.이 부분 연습이 필요할 것 같다.

 

---

코드

코드를 좀 편하게 짜려고 마지막 웅덩이는 별도로 체크하도록 했다. 이 때도 포인터 변수를 통해 앞에서 썼던 널빤지가 웅덩이를 덮어버렸는지 잘 체크해주면 된다.

 

def main():
    n, l = map(int, input().split(" "))
    rills = []
    for _ in range(n):
        start, end = map(int, input().split(" "))
        rills.append((start, end))
    rills.sort(key = lambda x: (x[0], x[1]))

    ptr = rills[0][0]
    answer = 0
    for curr, next in zip(rills, rills[1:]):
        start, end = curr
        width = end - ptr

        log_num = width // l
        if(width % l != 0):
            log_num += 1
        
        answer += log_num
        ptr = max(ptr + log_num * l, next[0])

    last_width = rills[-1][1] - max(ptr, rills[-1][0])
    if(last_width >= 0):
        answer += last_width//l
        if(last_width % l != 0):
            answer += 1
    print(answer)

if __name__ == "__main__":
    main()