이분 탐색의 정석 같은 문제이다.
이분 탐색의 개념이 헷갈릴 때마다 이 문제를 다시 보면서 기강 다잡자!!
문제 링크
https://www.acmicpc.net/problem/1654
문제 유형
이분 탐색
🌈문제
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.
이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다.
예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)
입력
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.
4 11
802
743
457
539출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.
200💡 아이디어
이 문제의 힌트는 다음과 같다.
802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.
사실 문제 유형을 보지 않고 이 문제를 도전한다고 생각하면 정말 어렵게 느껴진다. 기존에 영식이가 가지고 있는 랜선이 최소 길이로 최대 가짓수를 가질 수 있는 방법에 대하여 고민해 보아야 한다. 내가 가질 수 있는 랜선의 길이를 알아보아야 하니,
가장 낮은 랜선의 길이를 l로 잡아 1이라고 두고, 무작정 모든 랜선이 하나의 줄로 이어져 있다고 생각하고 모든 수를 합쳐 우리가 구해야 하는 개수인 N으로 나눈 값을 가장 긴 길이인 h로 둔다.
그리고 l이 h보다 작을 때까지만 while문을 돌린다. 이 때, 이분 탐색을 공부하면서 가장 많이 접하게 되는 mid, 즉 중간 값을 이용하여 계산을 수행합니다.
그리고 랜선의 길이가 입력받은 랜선 길이를 통하여 나올 수 있는 것인지 나누기를 통하여 확인하고, 그 cnt 값을 계산합니다.
N = 1일 때부터 하나씩 늘려서 계산을 하면 되는데 왜 high값과 low값을 더해 나누어 중간값을 구해서 정리를 할까? 이런 생각을 하게 될 수도 있다.
그것은 바로 시간 복잡도 때문으로 low값과 high값을 이용하여 mid값을 구하게 된다면 더욱 빠르게 계산을 할 수 있으므로 그런 것이다. 그렇기 때문에 이중 분할을 효율적으로 이용하여 문제를 해결해 보도록 하자.
👨💻 코드 작성
from sys import stdin
K, N = map(int,stdin.readline().split())
li = list(map(int,stdin.readlines()))
h, l = sum(li)//N, 1
while l <= h :
mid = (h+l)//2
cnt = sum([x//mid for x in li])
if cnt < N:
h = mid - 1
elif cnt >= N:
l = mid + 1
ans = mid
print(ans)