[백준/Python] 2141번(그리디)_우체국

📌문제 유형

그리디, 정렬(골드 Lv.4)

 

📌문제

2141번: 우체국

 

📌나의 문제풀이

- (시간초과로 실패) 전체를 다 순회 함

n = int(input())
total = []

for _ in range(n):
    total.append(list(map(int, input().split())))

total.sort(key = lambda x : -x[1])


result = []
cnt = 0
# max_idx까지만 반복
while cnt < len(total):
    ans = 0
    now_town = total[cnt][0]
    for j in range(len(total)):
        ans += (abs(total[j][0] - now_town) * total[j][1])
    result.append([now_town, ans])
    cnt += 1

result.sort(key = lambda x:x[1])
print(result[0][0])

 

📌 다른사람의 문제풀이

-아이디어 : 누적 인구수가 절반을 넘어가는 지점 찾기

• 이유 : 인구가 많으면 많을수록 거리값이 가산되기 때문에, 인구 수가 중요한 문제

import sys
input = sys.stdin.readline

villiage = []
all_people = 0

N = int(input())

for i in range(N):
    n_viliage, people = map(int, input().split())
    villiage.append([n_viliage, people])
    all_people += people

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

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

 

📌 리뷰 및 참고

[백준] 2141번 우체국 (파이썬)

 

[백준 2141번] 우체국(파이썬)

- 어떤 걸 곱하는지, 곱하면 커지는 값이 무엇인지 생각해보기