백준 피자굽기 (Python/Go)

문제 링크: www.acmicpc.net/problem/1756

1756번: 피자 굽기

 

이분탐색 문제입니다. 그런데 이분탐색 유형인걸 알아도 어떻게 이분탐색을 적용해야하는지 쉽게 떠오르지 않을만한 문제입니다.

이분탐색을 적용시키기 위해서는 처음 input으로 주어지는 오븐의 지름을 조금 변경시켜주어야 합니다.

문제 예제인 [5 6 4 3 6 2 3] 으로 예를 들어보겠습니다.

이걸 [5 5 4 3 3 2 2] 로 바꿔주면 됩니다. 왜냐하면 6짜리 피자는 어차피 위에 5가 있으면 들어갈 수가 없습니다.

즉, 주어지는 지름들을 for문을 돌면서 자신의 지름이 이전 지름보다 크면 변경시켜주어야 합니다.

이렇게 바꿔주면 정렬된 리스트가 되었으므로 이분탐색을 적용시킬 수 있습니다. 그러나 내림차순 정렬이기 때문에 이분탐색시 이걸 고려하여 코드를 작성해야합니다.

아래는 파이썬 코드입니다.

d, n = map(int, input().split())
oven = list(map(int, input().split()))
doughs = list(map(int, input().split()))
 
for i in range(1, len(oven)):  # 이분탐색 적용을 위해 적절히 변경
    if oven[i] > oven[i-1]:
        oven[i] = oven[i-1]
 
 
piled_loc = 0  # 도우가 어디 쌓이는지
lp, rp = 0, len(oven)-1
for dough in doughs:
    is_piled = False  # False로 남으면 도우를 더 못쌓는다는 뜻
 
    while lp <= rp:
        mid = (lp+rp) // 2
        diameter = oven[mid]
        if diameter >= dough:
            lp = mid + 1
            piled_loc = mid
            is_piled = True
        else:
            rp = mid - 1
 
    if not is_piled:
        piled_loc = -1
        break
 
    lp = 0
    rp = piled_loc - 1  # 도우가 쌓이면 rp값 갱신 
 
 
if piled_loc == -1:
    print(0)
else:
    print(piled_loc+1)

 

아래는 Go코드입니다.

package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
)
 
func ChangeOven(oven []int, d int) {
    for i:=1; i<d; i++ {
        if oven[i] > oven[i-1] {
            oven[i] = oven[i-1]
        }
    }
}
 
func BinarySearch(oven []int, dough, lp, rp, piledLoc int, isPiled bool) (int, bool) {
    for {
        if lp > rp { break }
 
        mid := (lp + rp) / 2
        diameter := oven[mid]
        if diameter >= dough {
            lp = mid + 1
            piledLoc = mid
            isPiled = true
        } else {
            rp = mid - 1
        }
    }
 
    return piledLoc, isPiled
}
 
func main() {
    var d, n int
    fmt.Scanln(&d, &n)
 
    oven := make([]int, d)
    doughs := make([]int, n)
 
    scanner := bufio.NewScanner(os.Stdin)
    scanner.Split(bufio.ScanWords)
 
    for i:=0; i<d; i++ {
        scanner.Scan()
        oven[i], _ = strconv.Atoi(scanner.Text())
    }
    
    ChangeOven(oven, d)  // 오븐 적절히 변경 (이분탐색을 위해)
    
    for i:=0; i<n; i++ {
        scanner.Scan()
        doughs[i], _ = strconv.Atoi(scanner.Text())
    }
 
    piledLoc := 0  // 도우 쌓인 위치
    lp, rp := 0, len(oven)-1
 
    for i:=0; i<n; i++ {
        dough := doughs[i]
        isPiled := false
 
        piledLoc, isPiled = BinarySearch(oven, dough, lp, rp, piledLoc, isPiled)
 
        if !isPiled {
            piledLoc = -1
            break
        }
 
        lp = 0
        rp = piledLoc - 1
    }
 
    if piledLoc == -1 {
        fmt.Println(0)
    } else {
        fmt.Println(piledLoc + 1)
    }
 
}
 

45번째 줄의 scanner.Split()을 이용하면 공백을 기준으로 input을 받을 수 있습니다.

scanner.Split(bufio.ScanWords) 적용 후에 scanner.Text()는 이 문제 예제기준으로는 숫자하나씩 return하게 됩니다.

처음에 scanner.Split()의 존재를 모르고 string전체를 받고나서 변경하려고 시도했는데 반죽의 개수가 최대 30만개이고 golang 내부 버퍼 사이즈 문제로 에러가 계속나와서 고생을 했습니다.

 

pypy3으로는 약 300ms, go로는 80ms가 나오는데 다른 문제에 비해 차이가 크지 않은거 같습니다.