[baekjoon] 백준 1654번(파이썬)

< 문제 >

1654번

< SOL >

import sys
input = sys.stdin.readline
from collections import deque

K, N = map(int, input().split())
line_list = deque()

for _ in range(K):
    line_list.append(int(input()))

minn = 1
maxn = min(line_list)

while True :
    need = 0
    mid = (minn+maxn)//2
    

    for i in line_list:
        num = i // mid
        need += num
    
    if need < N :
        maxn = mid-1
    
    elif need > N:
        minn = mid+1
    
    else:
        print(mid)
        break

이분 탐색 알고리즘이라고 생각하고 짰는데 시간 초과가 나왔다. 필요한 갯수가 N보다 작을 때는 최대값을 절반 줄이고 N보다 클 때는 최소값을 두배 늘렸는데 음.. 시간초과라니 더 생각을 해봐야겠다.

 

< SOL 2>

import sys
input = sys.stdin.readline
from collections import deque

K, N = map(int, input().split())
line_list = deque()

for _ in range(K):
    line_list.append(int(input()))

minn = 1
maxn = max(line_list)

while (minn <= maxn) :
    need = 0
    mid = (minn+maxn)//2
    
    for i in line_list:
        need += i // mid
    
    if need >= N :
        minn = mid+1
    
    else:
        maxn = mid-1

print(maxn)

평균을 낼 때 최대값을 min(line_list)로 했었는데 예제를 푸는데 문제가 없었다. 하지만 이분 탐색 정석(?)으로 최대값으로 코드를 바꿨다.

그리고 문제의 핵심인 while 문 안의 내용도 변경했다. while문을 True로 두고 돌렸는데 조건을 주고 코드 안 조건문도 부등호 방향에 따라 값이 달라지기 때문에 'need>=N'을 위로 올렸다.