★[python_파이썬_Pass]백준_2512번_예산_이분탐색_풀이

공부하는허딩크 : https://www.youtube.com/live/NQxG_GQn54s?feature=shared

 

와 어렵다.

고민 많이 했다.

<첫번째 시도 : 시간초과>

M이 10억이 최대치니까 아래의 코드는 시간초과가 날 것으로 예상했다.

#일단 상한액 밑으로는 모두 지급 후 상한액 이상인 것들은 상한액으로 고정

#그럼 budget을 다 더한 후 M과 비교해서 budget이 크면 max(budget) = 상한액 - 1을 계속 한다.

"""시간초과"""

import sys

input = sys.stdin.readline

N = int(input())

budget = list(map(int, input().split()))

M = int(input())

def budgets(data, M):

    adjust = max(data)

    while True:

        new_budget = []

        if sum(data) <= M:

            return max(data)

        else:

            adjust -= 1

            for i in data:

                if i < adjust:

                    new_budget.append(i)

                else:

                    new_budget.append(adjust)

        if sum(new_budget) <= M:

            return max(new_budget)

                   

print(budgets(budget, M))

 

<두번째 시도 : 틀렸습니다.>

파이썬에서 실행했을때부터 답이 이상했다. 일단 패스

#틀렸습니다.

# # #이진검색으로 budget안에 최소와 최대의 사이에서 움직일까?

import sys

input = sys.stdin.readline

N = int(input())

budget = list(map(int, input().split()))

M = int(input())

def budgets(data, M):

    start = 0

    end = len(data) - 1

   

    while start <= end:

        mid = (start + end) // 2

        max_budget = data[mid]

        new_budget = []

        result = 0

       

        for i in budget:

            if i < max_budget:

                new_budget.append(i)

            else:

                new_budget.append(max_budget)

       

        if sum(new_budget) <= M:

            start = mid + 1

        else:

            end = mid - 1

        return max_budget

   

start, end = min(budget), max(budget)

Data = list(i for i in range(start, end + 1))

print(budgets(Data, M))

 

<세번째 시도 : 틀렸습니다.>

이건 왜??? 파이썬에서 실행시 예시에 대한 정답이 정확하게 나왔는데.... 이진탐색은 최종 return을 어떻게 해야 하는지가 많은 고민이 필요하다. 그래서 예시를 한번 돌려서 어떤 값을 return해야 하는지 확인했다.

import sys

input = sys.stdin.readline

N = int(input())

budget = list(map(int, input().split()))

M = int(input())

max_b = list(i for i in range(min(budget), max(budget) + 1))

#[110, 111, 112, 113, 114, 115, 116, 117, 118, 119,      10개

# 120, 121, 122, 123, 124, 125, 126, 127, 128, 129,      10개

# 130, 131, 132, 133, 134, 135, 136, 137, 138, 139       10개

# 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150] 11개

def BS(arr, m):

    start, end = 0, len(arr) - 1 #0, 40

   

    while start <= end:

        total = 0

        mid = (start + end) // 2 # 20 (130), 9(119), 14(124), 17(127), 18(128)

        for i in budget:

            if arr[mid] <= i:

                total += arr[mid] #130, 130, 119, 119, 119, 124, 124

            else:                 #127, 127  

                total += i #120, 110 , 110, 120, 110, 120, 110

       

        if total == m:

            return arr[mid]

        elif total > m: #490 #486

            end = mid - 1 #20 - 1 = 19, 17

        else: #467 #478 #484

            start = mid + 1 #9 + 1 = 10, 15, 18

    return arr[end]

print(BS(max_b, M)

 

<네번째 시도 : 맞았습니다._chat gpt도움>

방향성은 거의 비슷한데 뭔가 다르네? 역시 이진탐색에서 어떤 값을 return해야 하는지 고민이 필요할 것 같다.

import sys

input = sys.stdin.readline

N = int(input())

budget = list(map(int, input().split()))

M = int(input())

def BS(arr, m):

    start, end = 0, max(budget)

   

    while start <= end:

        total = 0

        mid = (start + end) // 2

       

        for b in budget:

            if b >= mid:

                total += mid

            else:

                total += b

       

        if M < total: #예산 초과시 상한선을 낮춤

            end = mid - 1

        else: #예산이 남거나 딱 맞으면 상한선을 올림

            start = mid + 1

           

    return end #마지막으로 만족하는 end값이 최적의 상한선

print(BS(budget, M))