[백준] #2792 - 보석상자

2023/7/17

실버1

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

2792번: 보석 상자

 

 

🔎 분석

이분탐색 문제를 풀려고 선택한 문제. 이분탐색을 적용하면 되는 단순한 문제였다.

이분탐색이라고 생각하지 않고 문제를 보자마자 생각나는 대로 풀어봤는데, 가장 큰 값을 절반으로 나눠서 뒤에 추가하는 방식이었다. 이렇게 접근하면 예제는 잘 돌아갔지만, 시간초과가 뜬다. 시간초과가 뜨는 이유는 max를 구하는 과정이 너무 길어져서가 아닐까 생각했다.

 

✏️ 과정

어떻게 이분탐색을 적용해야 할까 고민했지만 잘 모르겠어서 검색해봤다 ㅠㅠ

보석을 mid로 나눠서 몫만큼의 사람에게 나눠주고, 나머지가 있다면, 1명에게 더 나눠주는 로직을 짰다.

이때, 보석이 남는다면(실제 사람 수보다 나눠주려는 사람 수가 많다면) 나눠주는 양을 더 늘려서(mid+1) 계산하고, 반대로 보석이 부족하다면 나눠주는 보석 양을 줄여서(mid-1) 더 많은 사람에게 나눠줄 수 있도록 했다. 이렇게 계산하다보면 l>r이 되는 시점이 나오고, 그게 답이 된다.

 

나무 자르기와 마찬가지로 재귀로 이분탐색을 적용하고 예제를 돌렸는데, 이상하게 return값이 제대로 안 나왔다. 이유는 재귀함수이다 보니까 우리가 원하는 답은 여러 중첩된 재귀함수 중 가장 안쪽에서 return되는데, 그 밖의 경우(l≤r)에서는 return 값이 없기 때문인 것 같다. 그래서 그냥 print 하도록 하여서 맞았습니다가 나왔다.

 

📍TIP

그리고 math 라이브러리를 썼는데 정답으로 처리됐다. 백준에서는 써도 되는듯!!

시간은 1136ms가 나왔는데, 나무 자르기 문제에서도 그랬듯 while문으로 풀었을 때는 2604ms로, 두 배가 걸렸다. 재귀로 푸는 게 더 빠르다!!

 

💻 코드

import sys
import math
input = sys.stdin.readline

N, M = map(int, input().split())
bosuk_list = [int(input()) for _ in range(M)]

result = max(bosuk_list)
l = 1
r = result

def binary_search(a, l, r, N, result):
    mid = (l+r)//2
    person_with_bosuk = 0

    if l <= r:
        for bosuk in a:
            # 보석 개수를 mid로 나눠줌
            quotient = bosuk // mid # 몫은 보석을 나눠줄 수 있는 사람 수
            remainder = bosuk % mid # 나머지는 남은 보석 수

            person_with_bosuk += quotient
            if remainder > 0:
                person_with_bosuk += 1
        if person_with_bosuk > N: # 나눠주려는 사람 수가 실제 사람 수보다 많으면 더 큰 값으로 나눠주야 함
            binary_search(a, mid + 1, r, N, result)
        else: # 나눠주려는 사람 수가 더 적으면 한 사람 당 더 작은 수의 보석을 나눠줘도 된다는 뜻
            result = min(result, mid)
            binary_search(a, l, mid - 1, N, result) 
    
    else:
        print(result)
    
binary_search(bosuk_list, l, r, N, result)