[python code review] 16주차 (기타 레슨, 공유기 설치, 예산)

[기타레슨]

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

2343번: 기타 레슨

[성공한 코드]

블루레이 크기를 mid로 두고 이진 탐색으로 풀이한다.

이때 블루레이 크기는 최소 1이어야 되니까 start는 1, 그리고 최대 크기는 길어봤자 전체 강의 길이이므로 end는 max(blue_rays)로 잡는다.  

그리고 블루레이 크기(answer)는 강의를 자를 수는 없기 때문에 아무리 작아도 최대 강의 길이(max(blue_rays)보다 작아선 안된다. 

# 크기가 mid인 블루레이 m개에 잘 담을 수 있는지 검사 
def include():
    global n, m, mid, answer

    target = 0
    count = 1

    for i in range(n):
        target += blue_rays[i]
        if target > mid: 
            target = blue_rays[i]
            count += 1
        # 필요한 블루레이 개수가 m개를 초과하는 경우 
        if count > m: 
            return False
    return True


n, m = map(int, input().split())
blue_rays = list(map(int, input().split()))

start, end = 1, sum(blue_rays)
answer = end

while start <= end:
    mid = (start + end) // 2 # 블루레이 사이즈 
    if include():
        end = mid-1
        answer = mid 
    else:
        start = mid+1
print(max(answer, max(blue_rays)))

[틀린 코드]

from collections import deque

def include():
    global m, mid, answer

    target = 0
    deq = deque(blue_rays)
    count = 0
    while deq:
        while deq and mid >= deq[0] + target:
            target += deq.popleft()

        target = 0
        count += 1

    if count <= m:
        return True
    return False


n, m = map(int, input().split())
blue_rays = list(map(int, input().split()))
start, end = 1, sum(blue_rays)
answer = 1e9

while start <= end:
    mid = (start + end) // 2
    if include():
        end = mid - 1
        answer = mid
    else:
        start = mid + 1
print(max(answer, max(blue_rays)))

틀린이유 : 블루레이 크기가 mid일 때 m개의 블루레이로 모든 강의를 담을 수 있는지 검사하는 include()를 구현하는데 deq을 사용했다. 이때 반례는 아래와 같다.

start가 1, end가 16일 때 mid는 8이다. 이때 블루레이 크기가 8인 경우, 필요한 블루레이 개수는 10개이다. 가지고 있는 블루레이 개수를 5(=m)를 초과하기 때문에 include 배열은 False를 리턴해야 한다. 하지만 현재 카운팅된 블루레이 개수가 m개를 넘는지 검사하는 조건이 while문 밖에 있기 때문에 무한루프를 돌게 된다.

12 5
7 3 3 10 4 8 7 9 2 2 12 2

[틀린 코드 해결]

from collections import deque

def include():
    global m, mid, answer

    target = 0
    deq = deque(blue_rays)
    count = 1
    while deq:
        if count > m:
            return False

        while deq and mid >= deq[0] + target:
            target += deq.popleft()
        target = 0
        count += 1
        
    return True


n, m = map(int, input().split())
blue_rays = list(map(int, input().split()))
start, end = 1, sum(blue_rays)
answer = end

while start <= end:
    mid = (start + end) // 2
    if include():
        answer = mid
        end = mid-1
    else:
        start = mid+1
print(max(answer, max(blue_rays)))

 

[공유기 설치]

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

2110번: 공유기 설치

[성공한 코드]

ㅇㅇㅇ

 

[예산]

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

2512번: 예산

[성공한 코드]

def binary_search(start, end):
    global answer

    while start <= end:
        mid = (start + end) // 2
        _sum = 0
        for budget in budgets:
            _sum += mid if budget > mid else budget
        if _sum <= m:
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


n = int(input())
budgets = list(map(int, input().split()))
m = int(input())
answer = 0

# 모든 요청액을 배정할 수 있는 경우
if sum(budgets) <= m:
    print(max(budgets))
# 그렇지 않은 경우
else:
    binary_search(1, max(budgets))
    print(answer)