2022.12.28 백준 랜선 자르기

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

1654번: 랜선 자르기

 

if max_num < division_num:
    division_num = max_num

while (True):
    # 각 선마다 몇개가 나올 수 있는지를 파악
    division_lists = list(map(lambda x: x // division_num, num_lists))
    # 만족하면 탈출 음.. 만족을 못 할 가능성이 있는지?
    if sum(division_lists) >= n:
        break

    new_division_lists = []
    # 각 선에서 1개가 더 나올라면 몇 cm 까지 줄어들어야하는지 파악
    for i in range(k):
        new_division_lists.append(int(num_lists[i] // (division_lists[i] + 1)))
    # 그중에서 가장 큰 걸로 다시 나누기 시작
    division_num = max(new_division_lists)

print(division_num)

 

최대 길이에서 숫자를 줄여가며 갯수를 맞추어 가는 방식을 사용했다

하지만 결국 특정 경우의 수에서는 거의 모든 거를 다 돌아야 해서 시간초과가 나왔다. 

 

 

방법을 찾던 중 이분탐색이라는 개념을 접하게 되어서 간단히 개념을 익히고 문제를 풀어보았다. 

이분 탐색에 대해서는 다음에 더 자세히 공부를 해서 적어 놓아야겠다.

import sys

input = sys.stdin.readline

k, n = map(int, input().split())

num_lists = []
num_lists = [int(input().strip()) for _ in range(k)]

lo = 1
hi = max(num_lists)
division_num = (lo + hi) // 2
#print("hi lo divi",hi,lo,division_num)

while (lo + 1 != hi and lo != hi):
    if sum(list(map(lambda x: x // division_num, num_lists))) >= n:
        lo = division_num
    else:
        hi = division_num
    division_num = (lo + hi) // 2
    #print("hi lo divi",hi,lo,division_num)
if sum(list(map(lambda x: x // hi, num_lists))) >= n:
    print(hi)
else:
    print(lo)

lo 와 hi 를 사용해서 반씩 줄여가면서 계산을 했다. 

마지막에는 //2 로 인한 손실로 hi가 되는지 안되는지 검사를 하고 출력을 했다.

while문의 and는 모든 랜선의 길이가 1일 때를 대비해서 넣어두었다.