[Python] 백준 - 1654 랜선 자르기

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

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

 

 

필요한 도구

 

 

1. 이분 탐색 알고리즘 - 좌, 우측 탐색 : 찾는 값이 없을 경우 가장 근접한 방향의 값을 출력하거나, 값이 여러 개일 경우에 가장 좌, 우 측의 값을 출력한다.

 

[Python] 백준 - 10816 숫자 카드 2 (이분 탐색)

- 이분 탐색 알고리즘 포스팅

 

문제해결방법

 

 

1. 주어진 랜선들을 잘랐을 때, 그 자른 길이로 몇개의 랜선을 만들 수 있으며, 그 갯수가 주어진 '필요한 랜선의 갯수 N'을 충족하고, 최대길이가 맞느냐를 판정하는 문제이다.

 

 

2. 이분 탐색은 $O(logN)$의 시간복잡도로 정렬된 검색 범위를 반씩 좁혀가며 답을 찾는 알고리즘이다. 이 문제에서는 변동되는 l, r 에 따라 mid(자르는 길이)가 변동되는 값이 된다.

 

 

주어진 랜선을 이 mid길이로 자르고 갯수를 구해 '필요한 랜선의 갯수 N'와 맞는지를 판단한다.

맞다고 하더라도 최대길이가 아닐 수도 있기 때문에, 그 갯수가 유지되는 범위를 고정시켜놓고, 최대길이를 찾아봐야 한다. 

 

 

3. 기존의 이분 탐색에서는 '갯수 N'과 mid값이 동일하다면 그대로 그 mid인덱스를 출력한다. 여기에서는 최대길이 또한 찾아봐야 한다. 

 

def bin_sol(arr, target):
    l, r = 1, max(arr)
    while True:
        if l > r:
            break
        mid = (l+r)//2
        cnt = 0
        for i in lan:
            if i >= mid:
                cnt += i//mid  # cnt가 크면 길이가 짧고, cnt가 작으면 길다.
        if cnt == target:      # cnt가 target가 동일하더라도 최대길이를 찾아야 되니, 
            l = mid+1          # l을 mid+1로 바꿔준다. (l-1은 target과 동일하다.)
        elif cnt > target:     # 이제부터 l이 커짐에 따라 mid가 커지며, cnt는 줄어들 것이다.
            l = mid+1          # cnt가 줄어들어 r이 계속 줄어들게 된다.
        else:                  # l은 우측의 값을 찾아가며, r이 l보다 작아진다면 탐색완료.
            r = mid-1          # 가장 우측의 값은 l-1, 혹은 r이 된다.
    return l-1

 

 

1) 위 이분 탐색 코드를 보면, 가장 우측값을 찾을 때는 if cnt == target: 일 때 리턴하지 않고, l = mid + 1로 다시 우측을 탐색한다.

l - 1 값은 지금까지 찾은 target 과 동일한 경우의 mid값이며, 그 것을 알아 놓고 우측으로 범위를 늘려보는 거다. 

 

 

a. 가장 우측의 값이 아니었을 경우에는 r 이 줄어드는 과정에서 또 맞는 mid값이 갱신되어 l 이 우측으로  자리를 잡아갈 것이다.

 

b. 가장 우측의 값이었다면 r 이 줄어들다가 mid값을 갱신하지 못하고, r = l - 1이 되고 while문이 종료된다. 저장된 l - 1이나 r 이 조건에 맞는 가장 우측의 값이다. (최댓값)

 

- 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def bin_sol(arr, target):
    l, r = 1, max(arr)
    while True:
        if l > r:
            break
        mid = (l+r)//2
        cnt = 0
        for i in lan:
            if i >= mid:
                cnt += i//mid 
        if cnt == target:
            l = mid+1
        elif cnt > target:
            l = mid+1
        else:
            r = mid-1
    return l-1

k, n = map(int, input().split())
lan = sorted([int(input()) for _ in range(k)])
print(bin_sol(lan, n))