[Python3] 백준 1166번 선물

사용 언어 - Python3

문제 - 선물

1166번: 선물

 

 

정답

이분 탐색 문제 (정답 맞춘 여부 X)

1. L, W, H를 구하려는 값 A로 나누었을 때 N보다 작거나 같아야하므로 A를 구하기 위한 이분탐색을 사용한다.

A는 최소 0개 부터 쵀대 max(L,W,H)개 까지 있을 수 있으므로, left = 0, right = max(L,W,H), mid = (left+right)//2 이다.

만약  N개의 상자를 모두 넣을 수 있다면(= N보다 작거나 같으면), left = mid

아니면, right = mid

범위를 줄이면서 탐색을 계속한다.

 

2. 출력

right 값을 소숫점 10까지 출력한다.

N, L, W, H = map(int,input().split())
left, right = 0, max(L,W,H)

while left <= right:
    mid = (left+right)/2
    if (L//mid)*(W//mid)*(H//mid) <= N :
        left = mid
    else:
        right = mid
print("%.10f"%(right))

 

 

 

---

레퍼런스

• 정답 참고

[백준][python] 1166.선물 - Binary Search

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부