백준 알고리즘 - 1654 - 랜선 자르기

---

틀린 코드

k, n = map(int,input().split())
a = []
for _ in range(k):
    a.append(int(input()))
num = sum(a)//n

while True:
    ans=0
    for i in range(k):
        ans += a[i]//num
    if ans==n:
        print(num)
        break
    num -= 1

답은 맞았지만 시간초과.

 

---

코드

k, n = map(int,input().split())

def Count(len): # 길이를 변수로 받아서
    cnt = 0
    for i in line:
        cnt+=(i//len)
    return cnt

line = []
ans = 0
largest = 0 # 랜선 중 가장 긴 값

for i in range(k):
    tmp = int(input())
    line.append(tmp)
    largest = max(largest, tmp) # 기존의 값과 새로운 값 비교

lt = 1
rt = largest

while lt <= rt:
    mid=(lt+rt)//2 # mid = 답이되는 랜선의 길이
    if Count(mid)>=n: # mid로 만들 수 있는 랜선의 수
        ans=mid
        lt = mid+1
    else:
        rt = mid-1

print(ans)

이분탐색으로 접근해야 시간 초과 없이 문제를 풀 수 있다.

 

첫 풀이와 다르게,

랜선의 길이를 '0', '최대 랜선 길이' 로 따로 변수를 지정해서 저장해주었고

 

최소 랜선 길이가 최대 랜선 길이와 같거나 작을 때까지 반복하여

이분 탐색을 통해 답이 되는 랜선의 길이를 찾았다.

 

확실히 이분탐색으로 탐색을 해야 시간복잡도가 줄어드는 것 같다.