문제

BOJ 1654: 랜선 자르기 https://www.acmicpc.net/problem/1654

풀이

조건

• K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다.
• 시간 제한 : 2초
• 이미 자른 랜선은 붙일 수 없다.
• 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정한다.
• 자를 때는 항상 정수길이만큼 자른다고 가정한다.
• N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다.

풀이 순서

• 시간복잡도를 고려하여 이분 탐색 방법을 선택했다.
• 랜선의 최대, 최소 길이를 사용해 중간값을 구한다.
• 구한 중간값으로 랜선을 잘라서 몇 개가 나오는지 확인한다.
  • 랜선 개수가 많이 나오면 mid(랜선 길이)가 짧다는 뜻이다.
    • 구한 랜선 개수가 구해야 하는 랜선 개수(N)와 같아도 가장 긴 랜선을 구해야 하므로 해당 분기를 반복한다.
    • 랜선의 최소 길이를 mid + 1로 갱신한다.
  • 랜선 개수가 적게 나오면 mid(랜선 길이)가 길다는 뜻이다.
    • 랜선의 최대 길이를 mid - 1로 갱신한다.
• while문 탈출 조건에 따라 랜선 최소 길이(mMin) - 1을 출력한다.

코드

K, N = map(int, input().split()) # K: 이미 가지고 있는 랜선 개수, N: 필요한 랜선 개수

lines = list()
for i in range(K):
    lines.append(int(input()))

lines.sort()
mMin = 1
mMax = lines[len(lines) - 1]

cnt = 0 # 랜선 개수

while mMin <= mMax:
    cnt = 0  # 랜선 개수
    mid = (mMin + mMax) // 2  # 중간값
    for line in lines:
        cnt += line // mid

    if cnt >= N: # 랜선 개수가 큼(많이 잘림) -> 랜선이 짧음 (최대 길이 찾아야 됨)
        mMin = mid + 1
    else: # 랜선 개수가 작음(적게 잘림) -> 랜선이 긺
        mMax = mid - 1


print(mMin - 1)

정리

• 시간복잡도를 생각하여 이분 탐색을 떠올리는 것이 중요하다고 생각한다.