[백준 2512] 예산

문제 출처 : https://www.acmicpc.net/problem/2512

 

렌선 자르기 문제와 비슷한 느낌이 드는 문제 입니다. 다빈치코딩 알고리즘에 넣기에는 중복적인 내용이라 블로그에 추가하였습니다.

문제 이해하기

예산이 낮은곳은 그대로 두고, 예산이 높은곳만 줄여나가며 총액보다 작게 만드는 문제 입니다.

이 문제는 일반적인 이분 탐색 문제와 다른점이 있습니다. 바로 예산을 증액할 필요는 없다는 것입니다. 예산의 총액이 신청한 예산보다 크다면 더이상 예산을 늘릴 필요 없이 최대값을 출력하면 됩니다. 이 부분만 주의하면 문제를 해결할 수 있습니다.

코드 작성

그럼 코드를 작성하며 문제를 해결해 보겠습니다.

입력 받기

N = int(input())
arr = list(map(int, input().split()))
M = int(input())

전체 도시의 수 N을 입력 받습니다. 그리고 각 도시에서 신청한 예산을 입력 받습니다. 마지막으로 국가의 예산 총액 M을 입력 받습니다.

이분 탐색

def solve():
    start = 0
    end = max(arr)

    ans = 0
    while start <= end:
        mid = (start + end) // 2

        total = 0
        for a in arr:
            total += min(a, mid)
        
        if total <= M:
            start = mid + 1
            ans = mid
        else:
            end = mid - 1
        
    return ans

print(solve())

시작과 끝값인 start와 end를 0과 max(arr)값으로 지정합니다. 처음에 start 값을 arr의 가장 작은 값으로 하였더니 틀렸습니다. 잘 생각해보니 arr의 가장 작은 값도 예산이 깍이는 경우를 고려하지 않아 생긴 문제 입니다. 가령 3개의 도시가 있는데 국가의 예산 총액이 300이고 각 도시마다 150씩 예산을 신청했다면 전체 도시의 예산을 100으로 깍아야 합니다. 이런 경우 start 값을 150으로 했다면 이분 탐색이 되지 않습니다. 따라서 시작 값을 0으로 해야 정상적인 이분 탐색이 가능합니다.

 

이제 이분탐색을 시작합니다. 이분 탐색을 수행할 시 비교를 진행할 값은 예산의 합계 total 입니다. 이 때 mid 값보다 낮은 예산 a 값은 그냥 더하고, mid 값보다 큰 예산은 mid만 더해줍니다. total의 값을 국가의 예산 총액 M과 비교를 합니다. total 값이 M 값보다 작다면 start 값을 mid + 1로 바꿔주고 M값보다 크다면 end값을 mid - 1로 변경합니다.

이 때 정답으로 출력할 값은 국가 예산 총액을 넘지 않는 도시의 예산 최대값 입니다. mid 값은 예산의 총액을 기준으로 커졌다 작아졌다 합니다. 따라서 total 값이 M 값을 넘지 않는 경우에만 저장되어야 합니다. 따라서 정답을 출력할 ans 값을 total보다 M이 작을 때에만 저장해 줍니다.

전체 코드

N = int(input())
arr = list(map(int, input().split()))
M = int(input())

def solve():
    start = 0
    end = max(arr)
    ans = 0
    while start <= end:
        mid = (start + end) // 2

        total = 0
        for a in arr:
            total += min(a, mid)
        
        if total <= M:
            start = mid + 1
            ans = mid
        else:
            end = mid - 1

    return ans

print(solve())