[Python] 백준 1654번 - 랜선 자르기

문제 https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

이분탐색 안 하고 그냥 풀어도 되지 않을까.. 하는 희망을 가지고 풀었는데

시간초과 났다. ㅎㅎ

코드도 수정해보고 pypy3로도 해봤는데 안 돼서 결국 이분탐색으로 풀었다. 

 

 

#이분탐색코드

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
lan = [int(input()) for _ in range(k)]

s = 1
e = max(lan)

while s <= e:
    mid = (s + e) // 2
    cnt = 0
    for i in lan:
        cnt += i // mid
    if cnt >= n:
        s = mid + 1
    else:
        e = mid - 1

print(e)

 

#시간초과코드

import sys
input = sys.stdin.readline

k, n = map(int, input().split())
lan = [int(input()) for _ in range(k)]

mx = sum(lan)//n
cnt = 0
while True:
    for i in lan:
        cnt += i//mx
    if cnt != n:
        mx -= 1
        cnt = 0
    else:
        break

print(mx)