[Go] 백준 1166번 선물 (이분 탐색)

문제

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

입력

첫째 줄에 네 정수 N, L, W, H가 주어진다.

출력

첫째 줄에 가능한 A의 최댓값을 출력한다. 절대/상대 오차는 10^-9까지 허용한다.

---

문제 풀이

문제 해석 및 계획

박스에 담을 수 있는 A크기의 박스의 수는 a*b*c로 나타낼 수 있을 것이라고 생각하였습니다. 이는 a*(a+s1)*(a+s2)로 나타낼 수 있습니다. 따라서 i를 1부터 증가시켜 i*i*i가 N을 넘지 않는 i가 a가 됩니다.

a를 구하였으니 b와 c를 조건에 따라 1씩 증가시키면서 N을 넘기는 값을 찾을 수 있을 것이고 a, b, c를 구하였다면 해당하는 길이 나누기 개수를 하였을 때 가장 작은 값이 A라고 생각하였습니다.

오답 노트

예제 입력에 대하여 만족하는 결과였지만 N이 400인 경우 i는 20이 되고 L, W, H가 2*4*50으로 주어지게 된다면 i는 20이 되어 문제가 발생합니다. 따라서 아래의 정답이 틀렸다는 것을 알게 되었습니다.

package main

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

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

	defer writer.Flush()

	var N int
	length := make([]float64,3)
	fmt.Fscan(reader, &N, &length[0], &length[1], &length[2])
	sort.Float64s(length)

	Num := []int{1,1,1}
	for i:=1 ; i*i*i <= N ; i++ {
		Num[1]=i
	}
	for {
		if Num[1] * Num[0] * Num[2] >= N {
			break
		}else {
			if length[0]/float64(Num[0]+1) > length[1]/float64(Num[1]) {
				Num[0]++
			} else if length[2]/float64(Num[2]+1) > length[1]/float64(Num[1]) {
				Num[2]++
			} else {
				if (Num[0]+1) * Num[2] < Num[0] * (Num[2]+1) {
					Num[0]++
				} else {
					Num[2]++
				}
			}
		}
	}
	for i:=0 ; i<3 ; i++ {
		length[i] /= float64(Num[i])
	}
	sort.Float64s(length)
	fmt.Fprint(writer,length[0])
}

정답

로직이 떠오르지 않아 알고리즘 분류를 확인하였고 이분 탐색이라는 것을 확인 후 아래와 같은 방법을 사용하였습니다.

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
)

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

	var N int
	len := make([]float64,3)
	fmt.Fscan(reader, &N, &len[0], &len[1], &len[2])
	
	left, right := 0.0, math.MaxFloat64
	rst := ""
	for i:=0; i<10000 ; i++{
		mid := (left+right)/2

		if int(len[0]/mid) * int(len[1]/mid) * int(len[2]/mid) >= N {
			left = mid
			rst = fmt.Sprintf("%.10f",mid)
		} else {
			right = mid
		}
	}
	fmt.Fprint(writer,rst)
}

---

느낀 점

알고리즘을 안다면 생각보다 쉬운 문제였습니다. 다양한 알고리즘 방식이 있으며 문제에 따라 사용하는 알고리즘이 다릅니다. 문제를 보고 어떠한 알고리즘을 사용하여야겠다는 생각이 잡히기 위하여 노력하여야 합니다. 비 전공자로서 전공자가 4년 동안 배운 내용을 단기간에 따라잡기 어렵다는 것을 알기에 더욱 노력하여야겠다고 생각되었습니다.