99클럽 코테 스터디 4일차 python TIL - 이분탐색(백준2512 예산)

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

 

• 오늘의 학습 키워드 : 이분탐색
• 공부한 내용

import sys

# 입력 처리
N = int(sys.stdin.readline().strip())  # 지방의 수
d = list(map(int, sys.stdin.readline().strip().split()))  # 각 지방의 예산 요청
M = int(sys.stdin.readline().strip())  # 총 예산

# 이분 탐색 초기 설정
start, end = 0, max(d)
answer = 0

# 이분 탐색 수행
while start <= end:
    mid = (start + end) // 2  # 현재 상한액
    result = 0  # 현재 상한액으로 배정할 수 있는 총 예산
    
    # 각 지방의 예산 요청에 대해 배정할 금액 계산
    for i in d:
        if i > mid:
            result += mid  # 상한액을 넘는 요청은 상한액으로 배정
        else:
            result += i  # 상한액 이하의 요청은 요청한 금액 그대로 배정
    
    # 총 예산이 M 이하인 경우, 더 높은 상한액을 시도
    if result <= M:
        answer = mid  # 현재 상한액을 가능한 답으로 저장
        start = mid + 1
    else:
        end = mid - 1  # 총 예산이 M을 초과한 경우, 상한액을 낮춤

# 최종 결과 출력
print(answer)

 

• 오늘의 회고
  • 이거 보자마자 생각한건 이분탐색으로 풀면 되겠다였다.
    end = max값으로 하고, start를 min 값으로 첨에는 설정했더니 틀렸다..
    왜냐,, 상한액이 제시된 값보다 더 작을 수 있으므로 그래서 그렇게 하면 안되었던거다,,
  • 오늘의 결론 이분탐색을 이렇게 했는데도 틀리는거 보면 좀..제대로 문제를 풀자~