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

ji-vvon·2021년 7월 31일

알고리즘(파이썬)

목록 보기

28/41

📝문제1. 백준 2512번(예산)

- 문제

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

- 나의 코드💻

from sys import stdin
# n : 지방의 수, m : 총 예산
n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
array.sort()

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행
result = 0
while(start <= end):
    total = 0
    mid = (start + end) // 2
    for x in array:
        if x > mid:
            total += mid

    if total > m:
        end = mid - 1

    else:
        result = mid
        start = mid + 1

print(result)

- 정답 코드💻

from sys import stdin
# n : 지방의 수, m : 총 예산
n = int(stdin.readline())
array = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
array.sort()

# 이진 탐색을 위한 시작점과 끝점 설정
start = 0  # start : 가장 적은 금액 0
end = max(array)  # end : 가장 큰 금액 max(array)

while start <= end:
    total = 0 # 총 지출액
    mid = (start + end) // 2
    for x in array:
        total += min(mid, x)

    if total > m: # 지출액이 예산보다 크면
        end = mid - 1

    else: # 지출액이 예산보다 작으면
        start = mid + 1

print(end)

- 비교 분석📖

05-1 에서 했던 떡볶이떡 문제랑 비슷한 것 같아 그렇게 해보려고 했는데 잘 코드가 작성되지 않았다. 이런저런 블로그들을 참고하며 코드를 수정했는데 떡볶이떡 문제랑 흐름이 비슷한 것은 맞는 것 같다.

📝문제2. 백준 17266번(어두운 굴다리)

- 문제

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

- 나의 코드💻

코드를 입력하세요

공유기 설치 문제와 비슷한 것 같아 그런 식으로 풀어보려고 했는데 구체적인 구현이 잘 되지 않았다.

- 정답 코드💻

from sys import stdin
# n : 굴다리의 길이, m : 가로등의 개수, x : m개의 설치할 수 있는 가로등의 위치
n = int(stdin.readline())
m = int(stdin.readline())
array = list(map(int, stdin.readline().split()))

# 가로등이 1개인 경우
if len(array) == 1:
    # 해당 가로등의 위치와 시작점, 끝점과의 두 거리 중 더 큰 값을 높이로 선정
    height = max(array[0] - 0, n - array[0])

# 가로등이 여러 개인 경우
else:
    # 초기 높이 : 시작점과 첫 가로등 사이의 거리
    height = array[0]
    for i in range(len(array)):
        # 끝에 가장 가까운 가로등이 비춰야 할 거리(?)
        if i == (len(array) - 1):
            tmp = n - array[-1]
        else:
            # 마주하는 가로등의 거리 (양 끝의 가로등 제외)
            a = array[i+1] - array[i]
            # 해당 거리를 2로 나눈 나머지가 홀수인 경우
            # 가로등의 높이가 1이 더 높아야만 사이의 모든 거리를 비출 수 있음
            if a % 2:
                tmp = a // 2 + 1
            # 해당 거리를 2로 나눈 나머지가 짝수인 경우
            else:
                tmp = a // 2
        height = max(height, tmp)

print(height)