[BOJ] 1114 - 통나무 자르기

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

BOJ - 통나무 자르기

문제 유형: 이진 탐색, 매개 변수 탐색

문제 난이도: Gold I

시간 제한: 2초

메모리 제한: 128MB

 

문제

벌목꾼 백은진은 나무를 종이 공장에 옮겨야 한다. 하지만, 통나무의 길이가 너무 길어서 트럭에 들어가지 않으므로, 여러개의 조각으로 나누려고 한다.

통나무의 길이는 L이고, K개의 위치에서만 자를 수 있다. 통나무를 자를 수 있는 위치가 주어진다. 이 위치는 통나무의 가장 왼쪽에서부터 떨어진 거리이다. 통나무를 자를 수 있는 횟수는 최대 C번이다.

통나무의 가장 긴 조각을 작게 만들고, 그 길이를 구해보자.

 

입력

첫째 줄에 세 정수 L, K, C가 주어진다. 둘째 줄에는 통나무를 자를 수 있는 위치가 주어진다.

 

출력

첫째 줄에 두 개의 수를 출력한다. 첫 번째 수는 가장 긴 조각의 길이이고, 두 번째 수는 그 때 처음 자르는 위치를 출력한다. 만약 가능한 것이 여러 가지라면, 처음 자르는 위치가 작은 것을 출력한다.

 

풀이

우선, 자를 수 있는 정보 배열을 정렬하고 중복값들을 제거한다.

그 뒤, parametric search를 이용해서 풀 수 있다.

조각 당 최대 길이 maxCutLen를 기준으로, 뒤에서부터 그리디하게 자르는 것을 시도하면 되는데,

이전에 자른 위치 last를 l로 초기화한다. 거꾸로 배열을 순회하면서, last - arr[i]가 maxCutLen보다 커지면, arr[i+1]에서 잘라본다.

만약 그러나 arr[i+1]이 arr[i]보다 크다면 유효하지 못하다.

남은 개수 cnt를 1 줄이고, last도 arr[i+1]로 바꾼다.

만약 cnt가 0이 되면, 순회를 탈출하면 된다.

 

순회가 끝나고, 남은 cnt가 있다면, 무조건 arr[0]이 last이다.

만약 last가 maxCutLen보다 크다면, 유효하지 못하다.

이 조건분기들을 통과했다면, last를 반환하면 된다.

성공했다면 더 짧은 길이로 시도하기 위해서 hi를 mid-1로, 실패라면 더 긴 길이로 시도하기 위해 lo를 mid+1로 하면 된다.

 

 

코드

Go

package main

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

func check(l, k, c, maxCutLen int32, arr []int32) int32 {
	last := l
	cnt := c

	for i := k - 1; i >= 0 && cnt > 0; i-- {
		if last-arr[i] > maxCutLen {
			if arr[i+1]-arr[i] > maxCutLen {
				return -1
			}
			cnt--
			last = arr[i+1]
			if cnt == 0 {
				break
			}
		}
	}

	if cnt > 0 {
		last = arr[0]
	}

	if last > maxCutLen {
		return -1
	}

	return last
}

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

	var l, k, c int32

	fmt.Fscan(reader, &l, &k, &c)

	mp := make(map[int32]bool)
	arr := make([]int32, 0)
	for i := int32(0); i < k; i++ {
		var x int32
		fmt.Fscan(reader, &x)
		mp[x] = true
	}
	for x, _ := range mp {
		arr = append(arr, x)
	}
	sort.Slice(arr, func(i, j int) bool {
		return arr[i] < arr[j]
	})
	k = int32(len(arr))

	lo := int32(arr[0])
	hi := l
	for i := int32(1); i < k; i++ {
		lo = max(lo, arr[i]-arr[i-1])
	}
	lo = max(lo, l-arr[k-1])

	a := hi
	b := int32(-1)
	for lo <= hi {
		mid := (lo + hi) >> 1

		if res := check(l, k, c, mid, arr); res != -1 {
			a = mid
			b = res
			hi = mid - 1
		} else {
			lo = mid + 1
		}
	}

	fmt.Fprintf(writer, "%d %d\n", a, b)
}