백준 2141번 : 우체국

2022. 1. 24. 22:51·알고리즘

https://www.acmicpc.net/problem/2141

 

2141번: 우체국

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

www.acmicpc.net

 

접근하기 굉장히 까다로웠던 문제. 풀이를 보고나서 이해했다.

 

일직선 상의 1차원 좌표에 N개의 마을이 있고 각 마을의 위치와 주민의 수가 입력으로 주어진다. 여기에 우체국을 세우려고 하는데, 각 마을에 살고있는 주민들이 우체국을 가기위해 이동해야 하는 거리의 총합이 최소인 위치에 세우려고 한다. 이때 우체국의 위치를 구하는 문제다.

 

문제의 예시에서처럼 3개의 마을 A마을(위치: 1, 주민: 3), B마을(위치: 2, 주민: 5), C마을(위치:3, 주민: 3)이 있다고 가정하면 위치 2에 우체국을 세우는 것이 각 마을사람들이 이동해야하는 거리(A마을(1*3) + B마을(0*5) + C마을(1*3))가 6으로 최소이다. 완전탐색으로 모든 위치에서 거리를 계산하기엔 우체국이 존재할 수 있는 위치의 범위가 너무 넓었다. 그런데 풀이를 보니 굳이 거리를 계산해 줄 필요가 없었다.

 

마을의 위치 기준으로 오름차순 정렬했을때 가장 왼쪽에 있는 마을(A라고 하자)에 주목하자. 그럼 우체국을 이 마을(A)에 설치했을때 각 마을사람들이 이동해야하는 거리의 총합을 X라고 해보자. 만약 A에서 오른쪽으로 1만큼 떨어진 곳(A+1)에 우체국을 설치한다면, A의 오른편에 위치한 그 주민들은 우체국이 가까워졌기 때문에 그 수 만큼의 이동해야하는 거리가 줄어들고 현재 A+1 위치에 있는 우체국의 왼편에 위치한 마을의 주민들은 더 멀어졌기 때문에 그 수 만큼 거리가 증가한다. 즉, 그때의 총 거리 = X - (우체국 기준 오른편의 주민들 수 - 왼편의 주민들 수)가 된다.  다시 말하면, 우체국을 오른쪽으로 이동할 수록 왼편보다 오른편 주민들의 수가 더 많으면 전체적인 거리는 계속 줄어들 것이다. 결론적으로 우체국을 오른쪽으로 점점 이동시키다가 총 거리가 이전보다 같거나 증가하게 되는 시점의 위치를 출력하면 된다.

import sys
input = sys.stdin.readline

n = int(input())
s = sorted([tuple(map(int, input().split())) for _ in range(n)])
p = [s[0][1]]
for i in range(1, n):
    p.append(p[i-1] + s[i][1])

for i in range(n):
    if p[-1] <= 2*p[i]:
        print(s[i][0])
        break
저작자표시 (새창열림)

'알고리즘' 카테고리의 다른 글

백준 2812번 : 크게 만들기  (0) 2022.01.26
백준 11000번 : 강의실 배정  (0) 2022.01.24
백준 2250번 : 트리의 높이와 너비  (0) 2022.01.20
백준 1774번 : 우주신과의 교감  (0) 2022.01.19
백준 2655번 : 가장높은탑  (0) 2022.01.16
'알고리즘' 카테고리의 다른 글
  • 백준 2812번 : 크게 만들기
  • 백준 11000번 : 강의실 배정
  • 백준 2250번 : 트리의 높이와 너비
  • 백준 1774번 : 우주신과의 교감
무슈후슈
무슈후슈
코딩은 창작이다.
  • 무슈후슈
    감성코드
    무슈후슈
  • 전체
    오늘
    어제
    • 분류 전체보기 (121) N
      • 알고리즘 (30)
      • IOS (26) N
      • Swift (4)
      • TIL (41)
      • CS (15)
      • 메모 (2)
      • 시플 (1)
      • RxSwift (2)
  • 블로그 메뉴

    • 홈
    • 태그
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    다이나믹 프로그래밍
    SWIFT
    python
    비동기
    이분 탐색
    codable
    ios
    파이썬
    MVVM
    그래프 탐색
    백준
    코딩테스트
    Realm
    그리디
    git
    github
    프로그래머스
    알고리즘
    풀이
    http
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
무슈후슈
백준 2141번 : 우체국
상단으로

티스토리툴바