백준 1166 선물 Python

🐸 문제 정보

1166번: 선물

 

🤖 알고리즘

이분탐색

 

⏱️ 풀이 시간

26.04m

 

📝 풀이

처음에 수학 문제라고 확신하고 풀었다.

이유는 (L / A) * (W / A) * (H / A) = N인 경우의 A 값을 찾으면 되니까... 하고 풀었으나 실패.

결국 검색의 힘을 빌렸고, 이분탐색 문제인 것을 알았다.

 

1. start는 0, end는 L, W, H 중 가장 큰 값을 선택
2. end의 최대 값과 비교했을 때 반복문 100번 정도 돌리기 가능 (2 ^ 100)
3. 블럭 개수는 (L / A) * (W / A) * (H / A)
   • 이 개수가 N보다 크거나 같다면 start = 블럭개수
   • N보다 작다면 end = 블럭개수

 

사실 이분탐색 문제는 아직도 어렵다.

DP가 점화식을 찾는게 어렵다면, 이분탐색은 어떤 경우에 이분탐색으로 풀어야하는지 잘 모르겠다.

오늘은 이분탐색을 부숴야겠다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n, l, w, h = list(map(int, input().rstrip().split()))
start, end = 0, max(l, w, h)

for _ in range(100):
    mid = (start + end) / 2
    cnt = (l // mid) * (w // mid) * (h // mid)
    if cnt >= n:
        start = mid
    else:
        end = mid

print(f"{end:.10f}")