백준 실버2 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 12분

K,N = map(int,input().split())
ans = 0
lines = []

for _ in range(K):
    lines.append(int(input()))

lines.sort()

start, end = 1, lines[-1]

while start<=end:

    mid = (start+end)//2
    tmp = 0

    for line in lines:
        tmp += line//mid

    if tmp>=N:
        start = mid+1
        ans = mid
    else:
        end = mid-1

print(ans)

현재 가지고 있는 선의 갯수(K), 잘라서 만들어야하는 선의 갯수(N), 갖고 있는 선별 길이들이 주어지고 동일한 길이로 잘라 N개 이상의 선을 만들 수 있는 길이의 최댓값을 구하는 문제입니다.🕊️🕊️🕊️

자를 수 있는 길이별 선의 갯수를 binary search로 탐색하여 어렵지 않게 해결할 수 있었습니다.

[다른 사람의 풀이1]

n, k = map(int, input().split())
# 랜선의 길이 담은 리스트
lan = [int(input()) for i in range(n)]
# 갖고 있는 랜선중 최대값
max_lan = max(lan)
# 후보군 담을 리스트
res = []

def binary(k, start, end):
	# 이분탐색 시작
    while start <= end:
        mid = (start + end) // 2
        cnt = 0
        for i in lan:
        	# 구해진 값으로 랜선을 잘라본다
            cnt += i//mid
        # 자른 랜선들이 k 보다 작다면 좀더 작게 잘라야함
        if cnt < k: 
            end = mid - 1
        # 조건을 만족하는 경우.
        else:
        	# 후보에 넣고 좀더 크게 만들어봄
            res.append(mid)
            start = mid + 1
# 이분탐색 함수 호출
binary(k,1,max_lan)
# 후보군에서 최대값 출력
print(max(res))

동일하게 이분 탐색으로 구현하되 자를 수 있는 길이들(res)을 모두 구한뒤 최댓값을 구하는 방식입니다.

[다른 사람의 풓이2]

import sys
input=sys.stdin.readline
k, n = map(int, input().split())
li=[0]*k
for i in range(k):
    li[i]=int(input())
standard = max(li)
res=0
def binary(low, high):
    if high<low:
        return
    global n
    global res
    mid=(low+high)//2
    temp=0
    for i in li:
        temp+=i//mid
    if temp>=n:
        res=mid   
        binary(mid+1, high)
    else:
        binary(low, mid-1)
binary(0, standard*2)
print(res)

또 유사하게 이분 탐색으로 구현하되 재귀함수, global 변수를 활용하여 구현한 풀이입니다.🐕🐕🐕

감사합니다.