https://www.acmicpc.net/problem/16401
풀이 과정
- 이분 탐색으로 나누어 줄 과자의 길이를 찾는다.
- 과자의 길이가 구간의 중간값일 때, 과자를 나누어줄 수 있는지 확인한다.
- 확인하는 방법은 모든 과자의 길이를 중간값으로 나눗셈한 값의 합이 나누어주어야 하는 인원 수보다 많거나 같은 경우 나누어줄 수 있는것이며, 반대인 경우 나누어줄 수 없는 경우이다.
- 예시로는.. (1, 3, 5, 7, 9)라고 하고 중간값이 3이라고 하면, 3, 5일때는 1명이고 7일때는 2명, 9일때는 3명 나누어줄 수 있으므로 총 6명 나누어줄 수 있다.
- 나누어줄 수 있다면 과자의 길이의 최댓값을 구해야 하므로 정답을 저장하고 중간값 기준 오른쪽 구간에 대해서 진행하고, 나누어줄 수 없다면 왼쪽 구간에 대해서 진행한다.
- 구한 과자의 길이를 출력한다.
- 구간의 초기값을 문제를 보고 잘 조정해주어야 한다.. 처음에는 단순하게 1000000으로 했다가 틀렸는데, 문제를 다시 보니 과자의 길이가 1000000000까지이므로 최대 1000000000까지 나올 수 있으므 맞추어서 조정해 주었다.
소스 코드
import sys
input = lambda : sys.stdin.readline().rstrip()
M, N = map(int, input().split())
snacks = list(map(int, input().split()))
def test(snacks, target, target_people_count):
people_count = 0
if target == 0:
return False
for snack in snacks:
people_count += (snack // target)
if people_count >= target_people_count:
return True
else:
return False
left, right = 0, int(10e9)+1
answer = 0
while left <= right:
mid = (left + right) // 2
if test(snacks, mid, M):
answer = mid
left = mid+1
else:
right = mid-1
print(answer)
'알고리즘[Python] > 백준 알고리즘' 카테고리의 다른 글
[ 1743 ] [ BFS ] 음식물 피하기 (0) | 2021.10.13 |
---|---|
[ 6550 ] [ Queue ] 부분 문자열 (0) | 2021.10.12 |
[ 14653 ] 너의 이름은 (0) | 2021.10.08 |
[ 2251 ] [ BFS ] 물통 (0) | 2021.10.07 |
[ 2812 ] [ Stack ] 크게 만들기 (0) | 2021.10.06 |