[Binary search] 랜선 자르기 - 백준

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

문제 접근 풀이

---

Binary search 문제는 내가 문제를 풀 수 있는 해결책이 여러가지 있는데

그 중 가장 문제의 솔루션을 만족시키는 가장 최선의 output을 찾는 유형들에서 많이 풀이되는 방법론입니다.

연습했던 유사한 문제로는 프로그래머스의 입국심사문제, h-index 문제가 있습니다. 

 

binary search에 있어 중요한 조건은

Lower bound가 Upper Bound와 역전될 때 종료 조건임을 늘 기억해야 합니다.

 

solution

---

문제는 다음과 같습니다.

 

주어진 랜선은 K개가 주어지고 이를 동일한 N개의 랜선을 만들어야 하는 문제입니다.

주어진 K개의 랜선을 적당한 간격으로 잘라내어 N개의 랜선을 만들되 적당한 간격을 최대가 되게 하는 문제입니다.

 

예제를 살펴보면 다음과 같습니다.

다음과 같이 4개의 랜선이 주어질 때 렌선은 다양한 간격을 통해 분할이 될 수 있습니다.

 

가령 100을 기준으로 분할을 한다고 했을 때 다음과 같이 값이 주어집니다.

즉, 총 24개의 분할을 하게 됩니다. 물론 11개 이상일 경우 11개로 치게 되지만 100이 최대의 간격이라는 것을 보장할 수 없습니다.

 

반면 300의 경우를 생각해봅시다.

300의 경우, 총 6개 밖에 되지 않아 문제의 조건이었던 11개를 충족시키지 못합니다.

즉 너무 크게 간격을 잡은 것입니다.

 

이렇게 적당한 간격 중 가장 큰 간격을 찾아야 하는 데

이 방법을 바로 이분 탐색을 통해 찾습니다.

 

일반 linear search는 문제 set이 큰 경우 time limit에 걸릴 수 있기 때문에

일반적으로 logn 알고리즘인 binary search를 활용합니다.

 

Lower bound의 경우 1로 가정하였고

Upper bound의 경우 모든 랜선을 하나로 합쳤을 때 이를 N개로 등간격 한 경우가 가장 크다고 가정하였습니다.

왜냐하면 그 이상으로 더 자를 경우 자명하게 N개보다 값이 적어지기 때문입니다.

 

코드는 다음과 같습니다.

k, n = [int(x) for x in input().split()]

n_list = [int(input()) for _ in range(k) ]

## L, U 설정
L = 1
U = sum(n_list)//n

while(L < U) :
    mid = (L+U)//2
    cnt = 0
    for lens in n_list :
        cnt += lens//mid
    if cnt < n :
        U = mid-1
    if cnt >= n :
        L = mid+1

## 최종 후보군을 추림
## 정확한 종료 조건을 찾기 어렵긴 했음..
final_list = []
for i in [L-2,L-1, L, L+1,L+2] :
    cnt = 0
    if i <= 0 : continue
    for lens in n_list :
        cnt += lens//i
    if cnt >= n :
        final_list.append(i)

print(max(final_list))

다만 문제점이 위에 코드에도 있듯

정확하게 딱 하나의 경우를 찾기가 어려웠어서 마지막 코드에 후보군 중에 찾는 과정을 거쳤습니다.

저 부분이 문제 풀이의 오점이라는 생각이 들었습니다.

 

Time complexity

---

n_list 구축 O(k)

m = sum(n_list)//n 이라고 하면

1~m 사이의 간격을 search

O(logm)

따라서 O(k) 시간 복잡도가 나오는 것으로 추측