[백준] 2141번 : 우체국

2141번: 우체국

2141번: 우체국

🤔 문제분석

그리디 유형 문제로 마을의 위치 기준으로 오름차순 정렬한뒤에 사람의 수를 더해가면서 (모든 마을사람들의 수 / 2) 보다 커질경우 그 마을은 우체국의 위치가 된다. 마을 사람들이 절반이 되었을때가 우체국의 최적의 위치가 된다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())

village = []
all_people = 0
for _ in range(N):
    x, people = map(int, input().split())
    village.append((x, people))
    all_people += people

village.sort(key=lambda x:x[0])

acc_people = 0
for i in range(N):
    acc_people += village[i][1]
    if acc_people >= all_people / 2:
        print(village[i][0])
        break

🎯 피드백 및 개선사항

그리디 유형의 문제로 처음에 해당 문제를 어떻게 풀어야할지 감을 잡지 못하였다. 이분탐색으로 문제를 접근하였고,,, 실패하였다. 문제를 정답을 찾아보니 그리디 유형의 문제였고, (모든 마을사람들의 수 / 2) 보다 커질경우 그 마을이 우체국의 위치가 된다.

역시 그리디 유형의 문제는 어렵다… 😢