📚 2141 - 우체국

우체국

이해

문제에서
각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다.
라는 말을 보고, 아 그러면 거리 x 인원 수로 해야겠구나 라는 생각을 했다.

현재 위치에서 (거리 x 사람 수)로 이분 탐색하니 틀렸다고 해서, 이해가 되지 않아 검색 하고 맞추고 나서
다시 문제로 돌아와서 몇 가지 예제를 돌려 봤는데 사람 수로 판결하면 되는 것이였다.

4
1 2
4 2
6 2
10 2

=> 4

4
1 2
4 2
6 2
20 2

=> 4

2
1 2
2 2

=> 1

4
2 4
8 2
9 2
11 4

=> 8

4
2 4
8 2
9 2
11 5

=> 9

4
1 4
5 2
90 2
100 4

=> 5

4
1 13
6 9
9 6
13 1

=> 6

4
1 20
6 9
9 6
20 1

=> 1

공식이 있는 것 같은데 구하지 못했다. 외우자!
지역와 그 지역에 있는 사람 수가 주어질 때, 각 사람들끼리의 지역 거리의 합 최소를 구할 때는 사람 수로 구하면 된다. 거리가 아닌 갯수로 구한다.

각각 물건 무게가 있고 물건의 개수가 주어질 때, 물건의 개수로 구하면 된다.

• 이 때, 이분 탐색으로 구현한다.
• 좌측 결과가 오른쪽 결과 보다 크거나 같을 때
• 마을 위치를 기준으로 결과 값을 구한다.

소스

import sys  
  
read = sys.stdin.readline  
  
n = int(read())  
  
village = []  
  
for _ in range(n):  
    a, b = map(int, read().split())  
    village.append((a, b))  
  
village.sort()  
  
start = 0  
end = n  
  
answer = float(1e9)  
  
while start <= end:  
    mid = (start + end) // 2  
    left = 0  
    right = 0  
  
    for i in range(0, mid+1):  
        left += village[i][1]  
  
    for i in range(mid + 1, n):  
        right += village[i][1]  
  
    if left < right:  
        start = mid + 1  
    else:  
		# right가 left보다 크거나 같다면
		# 거리가 같은 경우, 마을 번호가 앞서는 걸로 하여라.
        end = mid - 1  
        answer = min(answer, village[mid][0])  
  
print(answer)

골드 4 문제 치고는 많이 어려운 것 같다.