05-5. 이진 탐색 문제풀이

📝문제1. 백준 2417번(정수 제곱근)

- 문제

https://www.acmicpc.net/problem/2417

- 나의 코드💻

import math
from sys import stdin
n = int(stdin.readline())
m = math.sqrt(n)
print(math.ceil(m))

- 비교 분석📖

이진 탐색으로 어떻게 풀어야할지 통 모르겠어서 구글에 math 라이브러리를 검색해서 풀었다.

https://jinho-study.tistory.com/689
이진 탐색으로 푼 코드이다. 근데 수학? 이라 그런지 그 코드가 자세히 이해가 가진 않는다.

---

📝문제2. 백준 13702번(이상한 술집)

- 문제

https://www.acmicpc.net/problem/13702

- 코드💻

from sys import stdin
# n : 주전자의 개수, k : 총 사람 수
n, k = map(int, stdin.readline().split())
array = []
for _ in range(n):
    array.append(int(stdin.readline()))
array.sort()

start, end = 0, max(array)
result = 0
while start <= end:
    mid = (start + end) // 2
    count = 0
    for x in array:
        a = x // mid
        count += a
    if count < k:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

- 비교 분석📖

파라메트릭 서치 문제 같아서 이전에 풀었던 파라메트릭 관련 문제들을 참고하면서 풀었다. 문제가 갑자기 헷갈려 중간에 막혔는데 이 블로그를 참고해서 풀어낼 수 있었다.
https://blog.naver.com/kellygirl4028/222452314549

---

📝문제3. 백준 15732번(도토리 숨기기)

- 문제

https://www.acmicpc.net/problem/15732

- 코드💻

from sys import stdin
# n : 상자의 개수, k : 규칙의 개수, d : 도토리의 개수
n, k, d = map(int, stdin.readline().split())
array = []
for _ in range(k):
    array.append(list(map(int, stdin.readline().split())))

def dotori(pivot):
    total = 0
    for start, end, step in array:
        beta = min(end, pivot)
        if start <= beta:
            calc = (beta - start) // step + 1
            total += calc
    return total

def solution():
    lo, hi = 1, 1000000
    ans = 0
    while lo <= hi:
        mid = (lo + hi) // 2

        if dotori(mid) >= d:
            ans = mid
            hi = mid - 1
        else:
            lo = mid + 1
    return ans

print(solution())

- 비교 분석📖

https://handhand.tistory.com/178
참고 블로그