문제요약

시간 제한
2초

본문 요약
길이가 제각각인 K개의 랜선을 갖고 있을 때, 랜선을 모두 N개의 같은 길이의 랜선으로 만든다고 한다. 이때 랜선의 최대 길이는?

입력
첫째 줄에는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력
1 <= K <= 10000인 정수, 1 <= N <= 1000,000인 정수, K <= N, 랜선의 길이는 2^31 - 1 이하의 자연수

출력
첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

풀이

먼저 시간 제한이 2초인데 K와 N은 각각 최대 10000과 1000,000이고 랜선의 길이도 굉장히 클 수 있다. 따라서 사용할 알고리즘의 복잡도가 N * K 혹은 K^2 등과 같으면 시간초과가 발생할 수 있다.

이진 탐색

그래서 시간내에 문제를 풀기 위해서는 이진탐색을 응용해야한다.
결론적으로 풀이의 복잡도는 Klog(K)의 복잡도이다.
기존 이진 탐색에서 랜선의 개수를 구하는 코드가 추가된 것이다.

만들 수 있는 랜선의 최대 개수 (count)

count는 각 랜선에 현재 길이(mid)로 나눈 몫을 더하면 구할 수 있다.
즉 입력 받은 리스트의 각 요소를 mid로 나눈 몫을 모두 더하면 된다.

이진 탐색

0과 리스트의 최대값을 탐색의 초기범위로 설정한다. (mn, mx)
mid는 기존 이진탐색과 동일하게 탐색범위의 (최소값 + 최대값) / 2이다.
여기서 기존 이진탐색과 다른 점은 기존 이진 탐색은 찾고자 하는 값에 도달하면 바로 그 값을 반환하게 되지만, 이 문제에서는 그러면 안된다.

예를 들어 다음과 같은 입력이 있다고 했을 때,

4 11
802
743
457
539

190과 200은 모두 입력 조건인 11을 만족한다. 하지만 이 중 가장 큰 값인 200을 출력해야 한다.

따라서 count가 n과 같으면 그 값을 출력하는게 아니라 mn을 mid + 1로 바꿔서 count == n을 만족하면서 그 보다 더 큰 값이 있는지 탐색해야한다.
그리고 이 케이스일 경우, 종료됐을 때 mid와 mn은 원래 찾고자 했던 값보다 1이 크기 때문에 mx를 출력해야한다.

코드

#입력 받기
k ,n = map(int, input().split())
lan = []
for i in range(k):
    lan.append(int(input()))
mx = max(lan)
mn = 0
while (mx >= mn):
    count = 0
    #mid가 0이 되어 0이 분모가 되는 경우 방지
    mid = max((mn + mx) // 2, 1)
    for l in lan:
        count += l // mid
    if count >= n:
        mn = mid + 1
    else:
        mx = mid - 1
print(mx)

참고용 반례

풀면서 신경썼던 반례들을 정리해놓는다.

5 5
300
300
300
300
100
답: 150

1 1
1
답: 1

1 3
30
답: 10

4 4
16
16
16
16
답: 16

4 32
8
8
8
8
답: 1

복기용 틀린 풀이

복기용으로 틀렸던 풀이도 정리한다.
N을 그대로 탐색하게 되면 복잡도가 굉장히 커지므로 있을 수 있는 하한과 상한을 정하여 그 범위 안에서 탐색하고자 했다.
범위를 좁혀서 그 구간 내에서만 탐색한다는 아이디어였다.
먼저, 상한을 구하는 방법은 입력된 모든 랜선의 길이를 더하고 K로 나누면 구할 수 있다.
또 하한은 랜선의 길이의 최댓값을 K로 나누면 구할 수 있다.

입력 예시

4 11
802
743
457
539

802 + 743 + 457 + 539 = 2541
2541 / 11 = 231 --> 상한

랜선의 최대 길이 = 802
802 // 11 = 72 --> 하한

이렇게 구한 상한과 하한값 내에서만 탐색한다는 아이디어였다.

하지만 이렇게 좁힌 하한과 상한에서는 특정 케이스에서 복잡도가 굉장히 커져서 아쉽게도 시간초과가 발생했다. 이진탐색과 내 풀이를 적절히 섞어서 시간복잡도를 크게 줄이고자했지만 이 또한 반례가 생겨서 풀이를 변경했다.

반례

1000,000 10000
1000,000  1000,001 1000,1002 ...... 1999,999 (100만개의 입력)

이 때 상한은 1500,000 하한은 1000,000으로
이 때의 시간복잡도는 500,000 * 1000,000이 되어 시간복잡도가 굉장히 커지게 된다.

창의적인 풀이를 즐기는 편이지만, 이런 창의적인 풀이들이 기존의 근본있는 알고리즘보다 효율적인 경우는 드문 것 같다. 창의적인 풀이를 생각하는 능력도 좋지만 기존의 알고리즘을 잘 활용할 수 있는 능력을 기르는게 코딩테스트에서는 더 중요한 능력 같다.