백준 1911번 - 흙길 보수하기 (Go)

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

분석

이 문제는 물웅덩이들을 최소한의 널빤지로 모두 덮어야 하는 그리디(Greedy)  문제입니다. 널빤지의 길이가 고정되어 있으므로, 앞에서부터 차례대로 덮어나가는 것이 최선입니다.

시간복잡도는 물웅덩이의 개수 n이 최대 10,000개이므로, 물웅덩이를 시작 위치 기준으로 정렬하는 데 O(n log n), 그리고 정렬된 웅덩이를 한 번 순회하며 널빤지를 배치하는 데 O(n)이 소요됩니다. 전체 시간복잡도는 O(n log n)으로, 2초의 제한 시간 내에 여유롭습니다.

공간복잡도는 웅덩이 정보를 저장하는 데 int 형 O(n)이 필요하며, 8 byte * 10,000 * 2  = 약 160 KB 저장하므로 충분합니다.

 

알고리즘 로직을 정리하면 다음과 같습니다.

1. 정렬: 웅덩이의 시작 위치를 기준으로 오름차순 정렬합니다. 앞에서부터 덮어야 뒤쪽 웅덩이를 덮을 때 널빤지가 남는 부분을 최대한 활용할 수 있기 때문입니다.
2. 널빤지 배치:
   • 현재까지 설치된 널빤지가 끝난 지점을 cur 라고 합니다.
   • 다음 웅덩이의 시작 지점이 cur 보다 뒤에 있다면, 널빤지를 웅덩이 시작 지점부터 새로 깔아야 하므로 cur 를 웅덩이 시작 지점으로 갱신합니다.
   • 웅덩이의 끝 지점까지 덮기 위해 필요한 널빤지 개수를 계산합니다.
   • 설치한 널빤지 개수를 결과에 더하고, cur 를 마지막 널빤지가 끝나는 지점으로 업데이트합니다.

풀이 코드

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

type Water struct {
	start, end int
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, l int
	fmt.Fscan(in, &n, &l)

	waters := make([]Water, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &waters[i].start, &waters[i].end)
	}

	sort.Slice(waters, func(i, j int) bool {
		return waters[i].start < waters[j].start
	})

	res := 0
	cur := 0
	for _, water := range waters {
		if cur < water.start {
			cur = water.start
		}

		if cur < water.end {
			dist := water.end - cur
			cnt := dist / l

			if dist % l != 0 {
				cnt++
			}

			res += cnt
			cur += cnt * l
		}
	}

	fmt.Fprintln(out, res)
}

 

회고

좌표 값이 최대 10억까지 주어지므로 배열을 직접 만들 수는 없으며, 정렬된 웅덩이 리스트를 순차적으로 처리하는 방식이 필요합니다.