1654 랜선 자르기

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

1654번: 랜선 자르기

 

내 풀이(반례 보고 맞춤)

n, m = map(int, input().split())
ary = []
for i in range(n):
    ary.append(int(input()))

start = 1
end = max(ary)
answer = 0

while (start <= end):
    mid = (start+end) // 2
    
    total = 0
    for i in range(n):
        if ary[i] >= mid:
            total += ary[i] // mid
               
    #너무 짧게 짤랐다.
    if total >= m:
        start = mid + 1
        answer = mid
    else:
        end = mid - 1
print(answer)

이 문제 또한 어제 푼 문제와 유사하다. 그래서 똑같이 풀었는데 이 문제는 조금 달랐다. 맨 처음에 실수 한 점이 랜선은 0으로 자를 수 없는데 start를 0으로 설정했다. 문제에도 나와있듯이 start는 1부터 시작해야 한다. 그리고 for문에서 ary[i]와 mid를 비교할 때 처음에는 ary[i]가 mid보다 커야지만 자를 수 있다고 했는데, 생각해보면 같은 길이라도 자를 수 있다. 따라서 ary[i] >= mid로 해줘야 잘 수행된다.