[백준 23090번] 난민

난이도: 골드 I

문제 링크: https://www.acmicpc.net/problem/23090

23090번: 난민

 

백준 23090번 문제 난민

 

백준에서 새로 추가된 문제들을 보다가

모교 프로그래밍 대회에 나왔던 문제길래 한번 풀어 봤습니다.

 

x = 0을 따라서 강이 흐르고 있고, 정화 시설은 강 위에 설치하게 됩니다.

매번 설치된 모든 난민촌에서 정화 시설까지의 거리의 합이 최소가 되는 곳에 정화 시설을 설치하고, 거리가 최소가 되는 곳이 2개 이상 존재하는 경우, y값이 가장 낮은 곳에 설치하도록 합니다.

 

입력이 들어올 때마다 정화 시설을 설치할 장소와 거리의 총합을 새로 구해야 하기 때문에, 시간이 빠듯합니다.

루프를 조금만 잘못 돌려도 시간 초과에 걸렸습니다 ㅠ

 

제가 접근한 방법입니다.

우선 정화시설이 무조건 강 위에 설치되고, 강은 x = 0을 따라 흐르므로, 난민촌에서 강까지의 거리의 x값은 해당 난민촌의 x좌표의 절대값이 됩니다.

따라서 거리의 총합을 구할 때마다 x값은 단순히 x좌표의 절댓값을 더해 주면 됩니다.

 

y값의 경우, 모든 난민촌의 y값의 중간값을 선택하는 경우 모든 난민촌으로부터의 거리가 최소가 됩니다.

이 중간값을 구하기 위해서 저는 priority queue를 두 개 사용하였습니다. 이 글에서 사용한 방법과 동일합니다.

lower_y (내림차순)에는 중간값 이하의 y값을 넣었고, higher_y (오름차순)에는 중간값 초과의 y값을 넣었습니다.

lower_y의 top이 가리키는 값이 중간값이 됩니다.

 

현재 정수시설의 위치 (y좌표)가 L, 난민촌으로부터 정수시설까지의 거리의 합이 K라고 합니다.

이 때 y좌표의 값이 정수시설 이하인 난민촌의 수 (lower_y의 크기)를 S1, y좌표의 값이 정수시설 초과인 난민촌의 수 (higher_y)의 크기를 S2라고 합니다.

새롭게 추가된 난민촌의 좌표 (x', y'), 새 정수시설의 위치가 L'이라고 할때, 새롭게 구하는 난민촌으로부터 정수시설까지의 거리의 합 K'는

K' = K + |L - L'| * |S1 - S2| + |L' - y'| + |x'|

가 됩니다.

이렇게 하면, 이전에 계산해 두었던 K, L, S1, S2와 새롭게 얻은 L', x', y'를 이용해 K'를 상수시간 내에 계산할 수 있습니다.

 

이 문제의 포인트는 크게 세 부분이었던 것 같습니다.

 

1. x값은 문제의 답을 구하는데 핵심이 아님을 알고, y값의 중간값을 구하는 것이 최소임을 파악하는 것
2. 매번 입력이 들어올 때마다 적당한 시간복잡도 이내에 중간값을 구하는 것
3. 최단거리의 합을 적당한 시간복잡도 이내에 구하는 것

저는 1, 2는 쉽게 해결했는데 3번에서 애를 너무 많이 먹었습니다 ㅠㅠ

 

채점 결과

틀렸습니다는 말 그대로 로직이 틀린 부분이고,

시간 초과는 기준점으로부터 y값까지의 거리를 구할 때 루프를 돌리는 바람에 시간 초과에 걸린 케이스입니다.

한 문제를 15트 해서 푼건 처음이네요 ㅎㅎ;

점화식을 떠올리는 부분이 3번의 핵심이었던 것 같습니다.

 

참고한 글:

• https://www.acmicpc.net/board/view/76411#comment-125126
• https://anz1217.tistory.com/138