사용 언어 - Python3
문제 - 선물
1166번: 선물
민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에
www.acmicpc.net
정답
이분 탐색 문제 (정답 맞춘 여부 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))
- 정답 깃허브
GitHub - yyeongeun/codingtest: 코딩테스트 공부
코딩테스트 공부. Contribute to yyeongeun/codingtest development by creating an account on GitHub.
github.com
'Algorithm > 이분탐색' 카테고리의 다른 글
| [백준] 10815번 숫자 카드 (0) | 2023.11.03 |
|---|---|
| [Python3] 백준 1072번 게임 (0) | 2023.04.04 |
| [프로그래머스 lv 4] 징검다리 (0) | 2023.02.07 |
| [프로그래머스 lv 3] 입국심사 (0) | 2023.02.06 |
| [백준] 12015번 가장 긴 증가하는 부분 수열 2 (0) | 2023.01.23 |
댓글