[백준알고리즘] 1654번: 랜선 자르기 -Python

[백준알고리즘] 1654번: 랜선 자르기 -Python

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

1654번: 랜선 자르기

이분 탐색 문제이다. 점점 이분 탐색이 어려웠었다.. 아직은 어려운 게 아니지만..

 

사실 처음에는 코드가 더 지저분했다 ㅎㅎ;; 다른 분들의 코드를 참고해서 수정하게 되었다.

 

여기서 두 가지 더 수정할 수 있는 부분이 있다.

 

첫 번째로 sum([x//Len for x in line])에 해당하는 부분이다. 이 부분은 lambda를 이용해서 sum(map(lambda x:x//Len, line)) 이런 방식으로도 해결할 수 있다. 처음에는 후자처럼 lambda를 사용했었는데 이후 다른 분이 전자를 사용한 것을 보고 제출 후 속도를 비교해보았다. 후자가 더 빨랐는데 왜인지는 잘 모르겠다. 얼마 차이가 안 나기는 했다.

 

두 번째로 다른 분들은 cnt >= N 일때, minLen = midLen + 1을 적용하고 if midLen == minLen:에 해당하는 부분도 없다. 이거는 추가로 변수를 하나 더 두어서 midLen을 저장한 후에 minLen = midLen + 1을 하면 되고, 전형적인 Binary Search 방식이 된다. 이 부분도 수정해서 올릴까 하다가 그냥 올렸다.

 

그나저나 코드 올리는 거에 라인 넘버를 띄우도록 다시 시도해봐야겠다

 

import sys

K, N = map(int, sys.stdin.readline().split())
line = [int(sys.stdin.readline()) for _ in range(K)]

def binary_search():
    maxLen = max(line)
    minLen = 1

    while maxLen != minLen:
        midLen = (maxLen + minLen)//2
        if midLen == minLen:
            return maxLen if sum([x//maxLen for x in line]) >= N else minLen

        cnt = sum([x//midLen for x in line])
        if cnt >= N:
            minLen = midLen
        else:
            maxLen = midLen - 1

    return maxLen

sys.stdout.write(str(binary_search()))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다