[PS | 한 번에 맞자!] 백준 2285

0. 문제 설명

우체국

2285번: 우체국

---

1. 문제 생각

처음에는 맨허튼 거리와 같은 알고리즘을 생각했다. 각 마을에 포함되는 사람들의 수를 가중치처럼 여긴 후 
∑각 마을의 index * 사람들의 수/ ∑사람들의 수 로 해결하려고 했는데 한 번 틀렸다 😥 

아래 데이터를 조금 더 생각해보면 이 아이디어가 통하지 않음을 알 수 있는데 아래 데이터로 한번 생각해보면 좋다!

6
1 8
8 1
9 2
10 3
11 3
12 2

맨허튼 거리가 아닌 어떤 기준이 되는 값에서 왼쪽 오른쪽으로 시소를 기울이는 듯한 생각을 하면 좋은데 어떤 지점으로부터 왼쪽 부분들은 모두 인구가 적은 마을들이 모여있을 것이고 오른쪽으로 가면 인구가 많은 마을들이 모여있을 것이다. 이 기준이 되는 것은 결국 인구의 절반이 되는 마을 이므로 

결국 전체 인구의 절반이 넘어가는 index를 찾으면 된다.

---

2. 문제 구현

❎ 틀린 코드

N=int(input())
total_sum=0
people_sum=0
List=[]
for _ in range(N):
    a,b=map(int,input().split())
    total_sum+=a*b
    people_sum+=b
    List.append((a,b))
ans1=total_sum//people_sum
ans2=total_sum//people_sum+1

total1=0; total2=0
for i in List:
    total1+=abs(ans1-i[1])
    total2+=abs(ans2-i[1])

if total1<total2: print(ans2)
else: print(ans1)

✅ 정답 코드

N=int(input())
List=[]
total=0
for _ in range(N):
    a,b=map(int,input().split())
    List.append((a,b))
    total+=b
List=sorted(List, key = lambda x :x[0])
target=total/2
SUM=0
ans=0
for i in List:
    SUM+=i[1]
    if SUM>=target: 
        # print(SUM, target)
        ans=i[0]; break;

print(ans)

---

3. 한번에 풀었는가? X