[BOJ] 1756번 : 피자 굽기(Go, Golang)

문제 링크 : 백준 1756번

[문제 접근]

d와 n을 전부 탐색하면 시간초과가 나오게 되므로 최적화가 필요하다.
나는 n을 fix하고 반죽의 개수인 d를 이분탐색을 통해 구현했다.

이분탐색을 하기 위해서는 정렬이 되어 있어야하는데 오븐의 특징을 이용하면 된다.
넓이가 5인 오븐 밑에 넓이가 6인 오븐이 있어도 6짜리 피자는 절대 들어갈 수 없다. 즉, 자기 위에 있는 오븐보다 커도 의미가 없다는 뜻이다.
따라서 오븐의 넓이는 5 5 4 3 3 2 2 라고 할 수 있다.(위에서 오븐을 내려봤을 때 보이는 모양이라고 생각하면 쉬울듯)

저렇게 오븐의 넓이를 정렬해주고 이분탐색을 실행하는데 오븐의 넓이보다 피자의 넓이가 작거나 같으면 start를 올려주고 아니면 end를 내려주는 방식으로 들어갈 수 있는 넓이에서 가장 밑에 있는 오븐에 넣어주게 했다.
다음 피자를 넣을 때 end는 전에 넣었던 오븐의 index-1을 해주어 이미 있는 피자의 밑으로는 갈 수 없게 설정해주었다.

⭐ pos가 0일 때는 해당 피자가 오븐에 들어가지 못한 상황이므로 0을 출력해주면 된다.

[소스 코드]

package main

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

var (
	r    = bufio.NewReader(os.Stdin)
	w    = bufio.NewWriter(os.Stdout)
	d, n int
)

func main() {
	defer w.Flush()
	fmt.Fscan(r, &d, &n)
	oven := make([]int, d+1)
	pizza := make([]int, n+1)
	tmp := 0
	for i := 1; i <= d; i++ {
		fmt.Fscan(r, &oven[i])
		if i == 1 {
			tmp = oven[i]
		} else {
			if tmp < oven[i] {
				oven[i] = tmp
			} else {
				tmp = oven[i]
			}
		}
	}

	for i := 1; i <= n; i++ {
		fmt.Fscan(r, &pizza[i])
	}
	down := d
	check := true
	for i := 1; i <= n; i++ {
		start, end := 1, down
		pos := 0
		for start <= end {
			mid := (start + end) / 2
			if oven[mid] >= pizza[i] {
				start = mid + 1
				pos = mid
			} else {
				end = mid - 1
			}
		}
		if pos == 0 {
			check = false
			continue
		} else {
			down = pos - 1
		}
	}
	if check {
		fmt.Fprintln(w, down+1)
	} else {
		fmt.Fprintln(w, 0)
	}

}