BOJ(백준) 2512[예산]

안녕하세요! 오늘은 백준 온라인 저지의 문제 번호 2512번을 풀어보겠습니다. 이 문제는 주어진 예산 요청 리스트에서 총 예산을 초과하지 않도록 예산 상한선을 찾아야 하는 문제입니다. 아래는 문제를 해결하기 위한 접근 방법과 정답 코드입니다.

 

1. 문제 설명

 

주어진 예산 요청 리스트에서 각 지방의 예산 요청을 충족하면서도 총 예산을 초과하지 않는 최대 예산 상한선을 찾는 문제입니다.

 

문제 URL : https://www.acmicpc.net/problem/2512

2. 접근법

1) 입력받기: 예산 요청의 개수와 각 지방의 예산 요청 리스트, 총 예산을 입력받습니다.

2) 이진 탐색 초기화: 최소 예산 상한선과 최대 예산 상한선을 설정합니다.

3) 이진 탐색 수행: 중간값을 계산하여 예산 상한선을 조정합니다.

4) 결과 출력: 가능한 최대 예산 상한선을 출력합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# 입력받기
N = int(input())  # 예산 요청의 개수
arr = list(map(int, input().split()))  # 각 지방의 예산 요청 리스트
M = int(input())  # 총 예산

# 이진 탐색을 위한 초기화
low = 0             # 최소 예산 상한선
high = max(arr)     # 최대 예산 상한선
ans = 0             # 가능한 최대 예산 상한선

# 이진 탐색 시작
while low <= high:
    mid = (low + high) // 2 # 중간값 계산
    sum = 0                 # 현재 예산 상한선으로 배정된 예산의 합계

    # 모든 예산 요청에 대해 예산 상한선을 적용
    for i in arr:
        sum += min(i, mid)

    # 예산 합계가 총 예산을 넘는 경우
    if sum > M:
        high = mid - 1  # 상한선을 낮춘다
    else:
        ans = mid       # 현재 상한선을 가능한 값으로 저장
        low = mid + 1   # 상한선을 높인다

# 최종적으로 가능한 최대 예산 상한선을 출력
print(ans)

 

4. 코드 설명

1) 이진 탐색 초기화

• low: 최소 예산 상한선을 0으로 설정합니다.

• high: 최대 예산 상한선을 예산 요청 리스트의 최대값으로 설정합니다.

• ans: 가능한 최대 예산 상한선을 저장할 변수를 0으로 초기화합니다.

 

2) 이진 탐색 수행

• mid: low와 high의 중간값을 계산하여 현재 예산 상한선을 결정합니다.

• 각 예산 요청에 대해 min(i, mid)를 계산하여 예산 합계를 구합니다.

• 예산 합계가 총 예산 M을 초과하는 경우, high를 mid - 1로 조정하여 예산 상한선을 낮춥니다.

• 예산 합계가 총 예산 M 이하인 경우, ans에 현재 예산 상한선을 저장하고, low를 mid + 1로 조정하여 예산 상한선을 높입니다.

 

이 코드는 이진 탐색을 통해 효율적으로 예산 상한선을 찾아내며, 각 지방의 예산 요청을 만족시키면서도 총 예산을 초과하지 않도록 합니다. 이 문제를 해결하는 데 이진 탐색 기법을 사용한 것은 매우 효율적이고 적절한 접근법입니다.

5. Github으로 확인

 

coTest/BOJ/BOJ01_04_04_2512.py at main · pcy4196/coTest