백준 1166 : 선물 ( Python )

문제 링크

📌 사용 알고리즘 : binary search

이분탐색을 공부할때 꼭 풀어보면 좋겠다고 생각되었던 문제였습니다.

식을 구하는것은 크게 어렵지 않습니다.

if (L//mid)*(W//mid)*(H//mid)>=N

위 조건일때 start 값을 증가시키고 그렇지 않을때는 end 값을 감소시키면 됩니다.

다만 실수오차가 매우 엄격합니다.

def binary_search(start , end):

    while start+0.000000001<=end:
        mid = (start+end)/2
        if (L//mid)*(H//mid)*(W//mid)>=N:
            start = mid+0.00000001
        else:
            end = mid-0.00000001
    return start

처음엔 이런 식으로 구현했는데 시간초과를 받았습니다.

이분탐색에사 실수오차를 정밀하게 해야할때는 while 문 대신 반복문을 사용해야 합니다.

📌 코드

import sys,math
input=sys.stdin.readline
from functools import lru_cache
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

def binary_search(start , end):

    for i in range(100):
        mid = (start+end)/2
        if (L//mid)*(W//mid)*(H//mid)>=N:
            start = mid
        else:
            end = mid
    return end

N,L,W,H=MI()
print(binary_search(0,max(L,H,W)))