백준 1654 랜선 자르기

gmlwlswldbs·2022년 1월 17일
0

코딩테스트

목록 보기
120/130
k, n = map(int, input().split())
line = []
for _ in range(k):
    line.append(int(input()))

l = 0
r = min(line) + 1
ans = 0

while l <= r:
    mid = (l + r)//2
    tmp = line[:]
    i = 0
    num = 0
    while i < k:
        if tmp[i] >= mid:
            num += 1
            tmp[i] -= mid
        else:
            i += 1
    if num >= n:
        l = mid + 1
        ans = mid
    else:
        r = mid - 1

print(ans)
  1. 처음에 잘린 랜선의 개수를 저런 식으로 풀어놔서 시간 초과 + 코드 자체도 걍 틀림
k, n = map(int, input().split())
lines = []
for _ in range(k):
    lines.append(int(input()))

l = 1
r = 2**31
ans = 0

while l <= r:
    mid = (l + r)//2
    num = 0
    for line in lines:
        num += (line//mid)
    if num >= n:
        l = mid + 1
        ans = mid
    else:
        r = mid - 1

print(ans)

잘린 랜선의 개수를 구하는 방법을 간단하게 바꿨고 계속 틀렸다길래 뭔가 했더니
최소값 (l) = 0, 최대값 (r) = 100001 이런식으로 설정해서 틀림. 길이의 최소는 0이 아니라 1이고 최대값도 문제를 잘 읽어보면 2*31이다. 최대값은 랜선의 길이 중 최대값 (max(lines))로 해도 됨..

0개의 댓글