C++ 예제 (넥슨 프로그래밍 대회 문제풀이 3)

저번에 이어 4번째 NYPC 2018 예선 문제입니다.

링크 : 예선 1~2번 문제 풀이 (아이템구매, 승리팀 찾기)

링크 : 예선 3번 문제 풀이 (줄임말)

먼저 문제를 한번 살펴보겠습니다.

우물왕 김배찌

물 부족 국가의 어린이들에게 깨끗하고 신선한 물을 선물하기 위해 김배찌님은 마을에 우물을 파기로 했다.

N 채의 집이 있는 한 마을에 우물 하나를 파주려고 하는데, 이 우물이 각 집들에서 너무 먼 거리에 있다면 물을 길으러 오가는데 시간과 노력이 많이 들어서 효용성이 떨어진다. 따라서, 각 집들까지 거리의 제곱이 최소가 되는 위치에 우물을 파려고 한다.

즉, 우물의 좌표가 (x, y)이고 첫번째 집의 좌표가 (x1, y1) 이라면, 우물과 첫번째 집까지 거리의 제곱은 (x-x1)2 + (y-y1)2 이 된다. 비슷한 식으로 우물로부터 각 집까지의 거리의 제곱의 합을 구하면 (x-x1)2 + (y-y1)2 + (x-x2)2 + (y-y2)2 + ... + (x-xN)2 + (y-yN)2 이 되며, 이 값이 최소가 되는 좌표 (x, y) 에 우물을 파면 된다.

모든 집으로부터 거리의 제곱의 합이 최소가 되는 우물의 좌표 (x, y)를 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 이 마을에 있는 집의 수를 나타내는 자연수 N이 주어진다 (1 ≤ N ≤ 300,000).

그 다음 N 줄에는 한 줄에 하나씩 집의 좌표 (xi, yi)를 나타내는 두 정수 xi와 yi가 주어진다 (0 ≤ xi, yi ≤ 100,000,000).

출력 형식

출력은 한 줄에 두 실수 x와 y를 출력하는데, 이는 주어진 조건을 만족하는 우물의 위치 (x, y)를 나타낸다. 출력한 두 값이 모두 정답과 차이가 0.001 이내라면 정답으로 인정된다.

입력 예제

5
1 2
2 6
3 2
4 7
1 2

출력 예제

2.2 3.8

채점 방식

입력 케이스들 각각에 대해 동일한 점수가 배분된다.

여기까지가 문제의 설명입니다.

요약하면, 여러채의 집이 있는 동네에 우물을 한개 파려고 하는데 집의 2차원 좌표(x, y)가 제공되었을 경우, 우물위치가 모든 집들과 떨어진 거리의 제곱 합이 최소화 지점이어야 하는데, 그 위치가 어디인가 라는 문제입니다.

"거리의 제곱의 합" 어디서 많이 들어본듯한 말입니다.

분산을 구할때 편차 제곱의 합을 변량의 개수로 나누면 분산이 됩니다. 산포도를 볼때 많이 사용합니다.

근데 분산을 최소화 하는 대표값이 평균이므로, 이 문제는 평균을 구해서 풀면 됩니다.

참고로 편차는 변량(관측값)에서 평균을 뺀 값을 말하며, 표준 편차는 분산에 루트를 씌워 구합니다.

입력예제에서 나온 집의 위치는 아래와 같습니다.

[집 좌표]

보기 쉽게 좌표 평면 위에 그려 보겠습니다.

[2차원 평면위 집 좌표]

집들의 위치가 다음과 같다면 거리의 제곱의 합이 최소가 되는 곳(빨간 사각형)이 우물의 위치입니다.

그 위치는 바로 평균을 구하면 됩니다.

x와 y의 합을 구해 집의 수만큼 나누어 평균을 구합니다.

• X = (1 + 2 + 3 + 4 + 1) / 5 = 2.2
• Y = (2 + 2 + 6 + 7 + 2) / 5 = 3.8

답은 X가 2.2 , Y가 3.8 입니다.

이제 C++로 작성한 코드를 살펴보겠습니다.

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;

    __int64 sumX=0, sumY=0;

    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;

        sumX += x;
        sumY += y;
    }

    cout << sumX / static_cast<double> (n);
    cout << " ";
    cout << sumY / static_cast<double> (n) << endl;
}

먼저 좌표 개수를 입력 받습니다.

이어서, 좌표의 개수 만큼 반복하며, 입력받은 좌표를 sumX, sumY에 누적하고 반복문을 나가서 n으로 나누어 평균을 구해 출력합니다.

주의할 점은 문제에서 집의 수(n)가 (1 <= n <=  300,000) 이며, 거리가 (0<= x, y <= 100,000,000) 이므로 누적값이 int의 범위를 넘어는 일이 발생할 수 있으므로 8바이트(64bit) 정수형 타입인 __int64 or long long 을 사용해야 합니다.

아래는 코드의 실행 결과 입니다.

감사합니다.