[백준 1654] 파이썬 - 랜선 자르기

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

1654번: 랜선 자르기

## 조건

- 캠프 때 쓸 N개의 랜선을 만들어야 한다.
- 이미 자체적으로 가지고 있는 K개의 랜선을 이용하여 N개 이상의 랜선을 만든다.
- 항상 센티미터 단위로 정수 길이만큼 자르며, 만들 수 없는 경우는 없다.
- 최대 랜선 길이를 구하여라


## 접근방법

- 처음에는 평균값을 구한 후, -1씩 해주면서 주어진 개수를 만족시키는 값을 구하려고 하였지만 시간초과!
- binary search를 통하여 중간값을 계속해서 바꿔주며 원하는 결과값을 도출하였다.

- 이분 탐색에서 최적화를 위해 결정 문제로 바꾸는 매개변수 탐색을 이용해주어야 한다.

2022.10.06 - [ALGORITHM/알고리즘 알아보기] - [알고리즘] 이분 탐색, 매개변수 탐색

[알고리즘] 이분 탐색, 매개변수 탐색

 

단순 for문을 이용하여 브루트 포스를 사용하니 시간초과의 벽을 넘지 못하였다 ㅠ.ㅠ

# 시간초과
K, N = map(int, input().split())  
  
cable = [] 
start = 1
for i in range(K):  
    # 가지고 있는 케이블 길이 받아준다.  
    cable.append(int(input()))  
  
end = max(cable)

total = int(sum(cable) / N)  
  
for j in range(total,0, -1):  
    num = 0  
    for k in range(K):  
        num += cable[k]//j  
  
    if num >= N:  
        print(j)  
        break

 

UPPER Bound를 이용 

또한 모든 리스트를 순회하며 결과값이 작은 것에서 -> 원하는 랜선의 개수를 넘어가는 부분을 찾아준다.

따라서, middle이 아닌 end와 middle이 같아지는 값이 최댓값이 된다. 

import sys
sys.stdin = open('input.txt')
K, N = map(int, input().split())

cable = []
for i in range(K):
    # 가지고 있는 케이블 길이 받아준다.
    cable.append(int(input()))

# 시작, 끝, 중간점을 설정해준 후, 시작점과 끝점이 같을 때까지 실행 해주면 최대 길이 얻을 수 있다.
start = 1
end = max(cable)

while end >= start:
    middle = (end + start) // 2
    count = 0
    for i in cable:
        # 중간값으로 나눠 준 선 개수 기록
        count += i//middle
    # 만들고자 하는 개수보다 많다면 길이 +1 , 아니라면 -1
    if count >= N:
        start = middle + 1
    elif count < N:
        end = middle - 1

print(end)