https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그www.acmicpc.net
실버문제지만, 이분탐색 개념이 잘 안잡혀있어서 헷갈렸다.
시간초과를 피하기 위해, 이분탐색을 써야한다.
- 1 과 가장 긴 랜선의 값을 start, end로 놓는다.
2.(start+end)//2 , 즉 시작과 끝의 중간점을 랜선의 길이 (mid)라고 설정한다.
mid 길이로 만들 때, 조건을 검사하여 n개 이상의 수가 나온다면,최소 길이(start)를 mid+1 로 설정한다.
반대로 n개 미만이 나온다면, 최대 길이(end)를 mid-1 로 설정한다.
3.start를 mid로 놓고, 위 과정을 다시 반복한다.
이를 진행하다 보면, start가 end 보다 커지게 될 것이다. 그러면 그 시점에서 end의 값이 만들 수 있는 최댓값이다.
import sysinput = sys.stdin.readlinek, n = map(int, input().split())
lan = [int(input()) for _ in range(k)]start, end = 1, max(lan)
while start <= end: # 범위가 벗어나지 않을때까지 반복하면서
mid = (start + end) // 2 # 이분탐색을 위한 중간값 cnt = 0 for l in lan:
cnt += l // mid # 만들 수 있는 총 갯수
if cnt >= n: # 만들수 있는 갯수보다 크다면, 랜선길이의 최솟값을 mid로 잡고 다시 반복 (같아도 최댓값을 구하기 때문에 계속)
start = mid + 1 # 무한반복을 피하기 위함
else: # 갯수만큼 만들 수 없다면, 랜선길이의 최댓값을 mid로 잡고 다시 반복 end = mid - 1
print(end)