2023.01.28 예산 백준[파이썬]

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

2512번: 예산

 

import sys
input = sys.stdin.readline

def main():
    n = int(input().strip())
    prices = list(map(int,input().split()))
    total = int(input().strip())
    if sum(prices) <= total:
        print(max(prices))
        return
    left = 1
    right = max(prices)

    while left+1 < right:
        pos = (left + right) // 2
        sums = 0
        for i in prices:
            if i <= pos:
                sums += i
            else:
                sums += pos
        if sums <= total:
            left = pos
        elif sums > total:
            right = pos
    print(left)

main()

이분탐색 문제를 찾아서 풀어봤다. 문제를 보자마자 이건 이분 탐색으로 풀어야겠다 라는 생각이 드는 문제들은 실버 2~3 정도 되는 문제인거 같다. 먼저 처음부터 계산을 안해도 되는 거 부터 예외처리를 하고 시작했다. 그 이후에는 각각의 값이 아니라 기준 값만을 찾는 코드로 짰다. 각 좌표의 왼쪽과 오른쪽에서 반절씩 나누면서 기준값에 맞는지 안맞는지에 대해서 확인하면서 left 와 right의 좌표를 정해줬다. 물론 여기서 = 표시나 // , left가 답인지 right가 답인지를 명확하게 맞추기 위해서 몇번의 시행착오가 있었다. 

이분탐색은 이분탐색으로 풀 수 있는지 어떤 식으로 돌리고 조건을 설정해주는 지가 중요한거 같다. 다음에는 이분 탐색 중에서도 다른 문제들을 찾아봐야겠다.