백준 1654: 랜선 자르기 (Python)

 

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

1654번: 랜선 자르기

 

처음엔 제일 작은 수부터 시작해서 점점 길이를 줄이면서 잘라내고

자른 개수 >= N 이면 멈추는 방식으로 코드를 짰는데 틀렸다.

 

# 틀림

import sys

k, n = map(int, sys.stdin.readline().split())
cable = []

for i in range(k):
    cable.append(int(sys.stdin.readline()))

length = min(cable)
while True:
    cut = 0

    for i in cable:
        cut += i // length

    if cut >= n:
        break
    else:
        length -= 1

print(length)

 

그래서 반례 찾아보다가 모든 케이블을 다 쓰지 않아도 된다는 사실 발견,,

냅다 제일 큰 수부터 시작해서 위랑 똑같이 동작하게 바꿨다

그 결과는 시간 초과ㅋ

 

# 틀림

import sys

k, n = map(int, sys.stdin.readline().split())
cable = []

for i in range(k):
    cable.append(int(sys.stdin.readline()))

length = max(cable)
while True:
    cut = 0

    for i in cable:
        cut += i // length

    if cut >= n:
        break
    else:
        length -= 1

print(length)

 

다시 이진탐색으로 풀어줬다,,

 

# 최종 코드

import sys

k, n = map(int, sys.stdin.readline().split())
cable = []

for i in range(k):
    cable.append(int(sys.stdin.readline()))

start = 1
end = max(cable)

result = 0
while start <= end:
    cut = 0
    mid = (start + end) // 2

    for i in cable:
        cut += i // mid

    if cut >= n:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)

 

성공!

 

ㅎ.