BJ1654_랜선_자르기_python

1. 문제링크

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

2. 풀이 전 계획과 생각

< 정보 정리 >

1) 입력값: 랜선 개수 K, 필요한 랜선의 개수 N, K개 랜선의 길이
2) 출력값: 랜선 N개를 만들 수 있는 최대 길이
3) 제약조건:

- 1 <= K <= 10,000
- 1 <= N <= 1,000,000
- K <= N
- 1 <= K개 랜선의 길이 <= 2^31 -1

4) 예외케이스: 없음

< 공통 로직 >

• 시작점(1) 부터 끝지점(랜선 중 가장 긴 랜선)까지의 중간 지점을 찾아라.
• 중간 지점으로 모든 랜선을 나눌때의 랜선 개수를 찾아라.
• 랜선 개수가 N보다 작을 경우, 끝지점을 중간지점 -1 변경하라.
• 랜선 개수가 N보다 크거나 같을 경우, 시작점을 중간지점 + 1로 변경하라.

3. 풀이

import sys

def cut_lan_cables():
  k, n = map(int, input().split())
  lan = [int(sys.stdin.readline()) for i in range(k)]
  start, end = 1, max(lan)

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

  print(end)

cut_lan_cables()

4. 풀이하면서 막혔던 점과 고민

Binary Search를 사용해서 풀어야하는데 헷갈려서 개념부터 복습하고 풀었다.

5. 풀이 후 알게된 개념과 소감

여러 줄의 값을 입력 받을 수 있는 방법을 찾다가 sys.stdin.readline()을 사용하면 되는 것을 이번 문제를 풀때 알게되었다.