Baekjoon 문제 풀기 (1654번 : 랜선 자르기) Python

1654번 : 랜선 자르기

1. 문제읽기

---

이진탐색 알고리즘의 대표적인 문제(라고한다)

문제만 봤을 때는 구현하기 그다지 어렵지 않겠는데? 싶었다.
그러나 문제는 입력 값이 너무 크다는 것…
아무리 해도 시간초과를 피할 길이 없었다.
내가 한 코드에서 반례만 찾으면 될거같았는데!! 하고 결국 포기하고 검색해보니 웬걸 ㅋㅋㅋ절대 맞지 못할 문제였다.
그래서 정답 비율이 20프로구나.. ㅎㅎ…

2. 제출 코드

---

정답코드를 보고 생각해보니 그래도 비슷하게는 다가간 것 같다^^
라고 위안을 삼아본다..
이 문제를 보고 어떻게 이진탐색을 생각하는가! 가 관건인 것 같다.
동빈북에서는 일단 데이터가 정렬되어있고, 탐색 범위가 크면 의심해보라고 한다.
많이 풀다보면 익숙해지겠지?

시간 초과 & 틀렸습니다가 뜬 코드.. 참고용으로 남겨놓는다..

import sys

k, n = map(int, sys.stdin.readline().strip().split())


arr = []
for _ in range(k):
	arr.append(int(sys.stdin.readline().strip()))
min_line = min(arr)
ans = []

while min_line != 0:
	count = 0
	for line in arr:
		count += line//min_line

	if count == n:
		ans.append(min_line)
		break
	else:
		min_line -= 1

ans.append(int(max(arr)//n))
ans.append(int(sum(arr)//n))
print(max(ans))

3. 공부할 것

---

리스트로 랜선의 값들을 받아주는 것까진 똑같다.
start를 최소 수인 1로 설정하고, end를 최대 랜선 길이인 max(arr)로 설정한다.
그리고 while문을 돌리면서 자른 랜선 수가 n보다 크거나 같은 것은 너무 잘게 잘라서 랜선 수가 많이 나온 것이므로 길이를 증가시키고, 랜선수가 n보다 작다면 너무 크게 자른 것이므로 길이를 줄여준다. start가 end보다 커지면 반복문을 종료하고 end를 리턴한다.

import sys

k, n = map(int, sys.stdin.readline().strip().split())

arr = []
for _ in range(k):
	arr.append(int(sys.stdin.readline().strip()))

start = 1
end = max(arr)

while(start<=end):
	mid = (start + end)//2
	count = 0
	for line in arr:
		count += line//mid
	if count >= n:
		start = mid+1
	else:
		end = mid-1

print(end)