1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
이 문제 또한 이분탐색의 기본적인 문제이다.
문제에서 보면 랜선의 길이는 최대 2^31-1까지 될 수 있다고 했는데 이는 int 범위 내에서 가장 큰 값이다. 이처럼 이분탐색 문제는 어마어마한 범위를 주는 경우가 많다. 어차피 몇 번만 탐색하면 전 범위를 다 볼 수 있기 때문이다.
이분탐색 문제를 몇 개 풀고 나면 이분탐색의 기본 포맷이 잡힐 것이다. 아래와 같다.
- 먼저 문제의 상한과 하한 값 파악
- 이를 통해 mid설정 ( mid= (s+e)/2 )
- mid를 기준으로 계산 후 문제의 조건과 비교
- s또는 e변경을 통해 범위를 절반으로 축소
- 1-4 반복
이제 문제별로 3번 부분만 바꿔주면 된다. 이전 포스팅에서의 공유기 설치 문제는 두 집간의 거리 차이와 mid와의 비교를 통해 공유기 설치 여부 결정하였고, 이번 문제에서는 각 랜선을 잘라서 mid만큼의 길이를 몇번 만들 수 있는지를 파악하는 것이다.
예를 들어 mid가 200일때, 랜선의 길이가 830이라면 4개를 만들 수 있다. 830 나누기 200의 몫은 4이므로. 남는 부분은 문제에서 친절하게(?) 버린다고 했으므로, 몫만 취하면 되는 것이다.
<주요 내용>
이분탐색
<코드>
import sys
si = sys.stdin.readline
def main():
[k, n] = [int(e) for e in si().split()]
l = []
for _ in range(k):
l.append(int(si()))
s, e, mx = 1, 2**31-1, 0
while s != e:
mid = (s+e)//2
cnt = 0
for elem in l:
cnt += elem//mid
if cnt >= n:
s = mid+1
mx = max(mx, mid)
else:
e = mid
cnt = 0
for elem in l:
cnt += elem//s
if cnt >= n:
mx = max(mx, s)
print(mx)
if __name__ == '__main__':
main()
