2024-07-13🙈 TIL - 백준 1166:선물

🔗 1166: 선물

 

이분탐색 문제인데 진짜 사고력이 코딩 챌린지 하면서 조금 늘었던게 제자리 된게 느껴졌다.

원리는 파악했는데 너무 코드가 지저분해 지면서 논점이 흐려지는.... 흐엉..

 

다시 머리를 사용해야겠다..

 

알고리즘은 다음과 같았다. 

(L//A)*(M//A)*(H//A) >= N

 

이것을 만족하면 되는데 최댓값 A를 구하라고 했으므로 

up : L, M, N 의 최솟값, down : 0 으로 지정하고 시작한다.

결과값이 N보다 크면 down을 mid로 끌어올려준다.

N보다 작으면 up을 mid로 내려준다. 

 

여기서 up, down은 가능한 A의 영역을 지칭하며 A가 클수록 결과값은 작아진다. 

그래서 그 영역을 점점 줄여나가다가 어느순간 멈춰야 하는데 처음에는 while True로 했는데 멈출 방법이 떠오르지가 않았다.

그래서 그냥 100번으로 했더니 통과했다. 오차범위도 있으니 적당히 가까워지면 되는 듯 하다.

 

import sys

N, L, M, H = map(int, sys.stdin.readline().split())

A = float(min(L, M, H))

down = 0
up = float(min(L, M, H))
for _ in range(100):
    mid = (down + up) / 2
    if (L//mid)*(M//mid)*(H//mid) >= N:
        down = mid
    else:
        up = mid
print(up)