[백준] 2792번 - 보석 상자 (파이썬)

< 백준 - 2792번 보석 상자 - 파이썬 풀이 >

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 먼저 문제에서 요구하는 것에 대해 알아보자. 해당 문제는 보석의 종류, 보석 갯수 그리고 학생의 수가 주어졌을때, 질투심이 최소가 되게 학생들에게 나누어주는 방법을 구해야하는 문제이다.( 질투심 = 가장 많은 보석을 가진 학생이 가진 보석 수 )
• 보석을 나누어주기 위해선 순차탐색을 통해서 반복하면서 보석이 없어질때까지 나누어주는 방법이 처음에 생각이 난다.
• 하지만 문제에서 입력으로 학생 수가 최대 10억(10^9), 보석의 종류가 최대 30만(300,000)이기 때문에 위와 같은 방법으로 풀면 시간 초과가 발생할 것이라 생각한다.
• 그래서 다른 방법을 찾아봐야하는데 이 문제를 들여다 보면 결국은 특정 조건에서 만족하는 가장 작은 최솟값을 찾는 문제이다. 그래서 이를 파라메트릭 서치를 이용하여 풀 수 있다. 파라메트릭 서치는 최적화 문제를 결정 문제로 바꿔서 푸는 기법이다. 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에서 주로 사용된다.
• 해당 문제에서는 한 학생에게 같은 색상의 보석만 줘야한다는 조건이 있고 이를 이용해서 가장 알맞은 값인 질투심의 최솟값을 찾아야한다.
• 그렇다면 결정 여부를 나타내기 위해선 어떤 조건으로 물었을 때, 그 결정 ( Yes or No )가 나와야하는데 해당 문제에선 어떤 조건으로 물어봐야할까? 어떤 값으로 보석을 나눠서 학생들에게 나눠줄 수 있는가?라고 물어야한다. 7명 중 5명에게 나눠주는 경우는 가능한 경우지만 7명에게 나눠줘야하는데 8명 분으로 나눠버리면 나눠줄 수 없는 경우가 되는 것이다.
• 나눠줄 수 없게 되면 분할을 하는 갯수를 늘려야하고 나눠줄 수 있다면 최솟값을 찾기위해 해당 값을 저장하고 분할 갯수를 줄여봐야한다. 이 과정에서 분할 갯수를 찾기 위해 이분 탐색을 사용할 것이다.

구현코드

def divide(start, end):
    while start < end: # 이분탐색
        mid = (start + end)//2
        sum = 0
        for index, j in enumerate(jewel): # mid 값으로 분할했을때 몇명에게 나눠줄 수 있는가?
            sum += (j//mid)
            if j%mid > 0: # 같은 색상만을 가질 수 있기 때문
                sum += 1
        if sum <= N:  # 학생 수 보다 더 적거나 같게 분할되었다면 해당 값을 저장. -> 같은 경우를 배제하면 안되기에 end = mid - 1이 아닌 end = mid로 표현
            end = mid
        else: # 학생 수보다 더 많이 분할되었다면 분할하는 갯수를 더 키워야한다.
            start = mid + 1
    return end # end를 반환해준다.

if __name__ == "__main__":
    N, M = map(int, input().split())
    jewel = [int(input()) for _ in range(M)]
    print(divide(0, sum(jewel)))