[Python] 99클럽 코테 스터디 2일차 TIL - 랜선 자르기

 

오늘의 학습 키워드

#이분탐색

공부한 내용 본인의 언어로 정리하기

이분탐색은 중간값을 구해서 크면 그 사이 범위에서 숫자를 찾고 작으면 그 아래 범위에서 숫자를 찾으며 항상 중간 값을 기준으로 숫자를 찾는 탐색 알고리즘이다.

오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했나요?

헣. 시도조차 못했다. 문제를 아무리 풀려고 해도 어떻게 풀어야할지 모르겠어서 30분 정도 고민하고 다른 블로그를 찾아서 답을 봤다. 

k, n = map(int, input().split())
nums = [int(input()) for x in range(k)]
start, end = 1, max(nums)

while start <= end:
  mid = (start + end) // 2
  lines = 0
  
  for i in nums:
    lines += i // mid
    
  if lines >= n:
    start = mid + 1
  else:
    end = mid - 1

print(end)

어떻게 해결했나요?

결국 이분탐색을 하면서 1부터 가장 긴 랜선 사이의 최적의 랜선의 길이를 찾는 문제였다.

nums를 결국 순회해야해서 시간 초과될 줄 알았는데 풀려서 신기했다.

무엇을 새롭게 알았나요?

사실 친구도 같이 향해99를 하고 있는데 친구가 먼저 올린 TIL 제목에 이분 탐색이라고 적혀 있어서 이분 탐색 문제인줄은 알고 있었다. 그런데 시도조차 안해서 못 푼 게 조금 아쉽다.