[백준] 1654번 랜선 자르기

사용 언어 - Python3

1654번: 랜선 자르기 (실버2)

문제 ★LG CNS 20년 하반기 코테 문제랑 유사★

1654번: 랜선 자르기

정답

이분 탐색 문제 <내가 생각하지 못한 아이디어>

(코드 설명)

1. import sys / sys.stdin.readline()

여러줄 또는 반복문으로 입력 받는 경우는 input()은 시간초과가 발생할 수 있기 때문에 sys를 사용한다.

주피터는 오류가 나타난다. stdin 지원안하는 듯? 파이썬에서 직접 하자ㅠㅠ

2. 이진 검색 알고리즘

예제처럼 lan 값이  802이면 802보다는 작은 정답이 나와야하므로, start = 1, end = max(lan) !

1부터 max(len)까지 다 반복하긴 시간 복잡도가 높아지므로, start와 end 중간 값인 mid를 정한다.

mid 값으로 lan 값 전체를 나누어서 합했을 때, 그 값(lines)이 N개 이상이라면 mid를 한개 증가시켜서 다시 반복한다. 만약 N개보다 작다면, end를 한개 줄여서 다시 반복한다.

한개 줄이지 않고 해도 되지만, 굳이 이미 답이 아니라고 검증된 mid 값을 재검정할 필요는 없기 때문에 범위에서 제거시킨다.

위와 같은 방식으로 계속 절반씩 범위를 줄여가면서 start <= end를 만족할 때까지 반복문을 진행한다.

start == end 를 넘어서 end = start +1이 되는 순간의 end를 출력한다.

 

보충 설명

# 정답

import sys

K, N = map(int,input().split()) #필요한 랜선의 수 N, 총 랜선의 개수 K
lan = [int(sys.stdin.readline()) for _ in range(K)] #랜 개수
start, end = 1, max(lan) #반복문 범위 지정

while start <= end:
  lines = 0 #N개여야하는 랜선 수
  mid = (start+end)//2 #중간값 (몫)
  for i in lan:
    lines += i//mid #mid으로 나눴을 때의 몫을 전부 구한다.
  if lines >= N:
    start = mid+1
  else:
    end = mid-1

print(end)

 

---

레퍼런스

• sys.stdin.readline() 사용법

[Python] 파이썬 sys.stdin.readline() 입력 받기 : 시간 초과 해결, 입출력 속도 개선

• 문제 정답

#390 백준 파이썬 [1654] 랜선 자르기 - 이분탐색

[백준 1654 파이썬] 랜선 자르기 (실버3, 이분 탐색)

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부