7571 점 모으기

 

 

이걸 네 점의 평균 위치에 점을 옮기면 가장 거리가 짧을 것 같았다. 근데 틀림ㅠ

 

다음으로 평균을 구할 때 무조건 나누면 내림이 되니깐 여기서 문제가 발생하지 않을까? 싶었다. 

 

그래서 (내림, 내림) (내림, 올림) (올림, 내림), (올림, 올림) 네 가지 경우를 모두 계산했는데 그래도 틀렸다ㅋㅋ

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int     calc(ii a, ii b)
{
    int ans = 0;
    ans += abs(a.xx - b.xx);
    ans += abs(a.yy - b.yy);
    return ans;
}

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    vector<ii> v(m);
    for (int i = 0; i < m; i++)
        scanf("%d %d", &v[i].xx, &v[i].yy);

    ii sum;
    sum.xx = 0;
    sum.yy = 0;
    for (int i = 0; i < m; i++)
    {
        sum.xx += v[i].xx;
        sum.yy += v[i].yy;
    }

    sum.xx /= m;
    sum.yy /= m;

    int ans = 0;
    for (int i = 0; i < m; i++)
    {
        ans += calc(sum, v[i]);
    }
    printf("%d\n", ans);
    
    return 0;
}

 

글 적으면서 생각난 건데 옛날에 비슷한 문제를 푼 것 같다?

 

ucpc 연습하면서 푼 것 같은데.. 점의 최소 거리를 구하는 문제 였는데 점을 기준으로 잡으면 그 점의 길이는 0이 되니깐 점마다 거리를 구했었다.

 

어엄....

 

점 위에다 거리를 구한다고 최소는 아니구나

 

 

 

아..! 평균이 최소가 아닌 건 알겠다

 

내림 올림 이것만 고려하면 될 것 같은데 구현을 잘못했나?

다시 확인해봐야겠다.

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int     calc(ii a, ii b)
{
    int ans = 0;
    ans += abs(a.xx - b.xx);
    ans += abs(a.yy - b.yy);
    return ans;
}

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    vector<ii> v(m);
    for (int i = 0; i < m; i++)
        scanf("%d %d", &v[i].xx, &v[i].yy);

    ii sum;
    sum.xx = 0;
    sum.yy = 0;
    for (int i = 0; i < m; i++)
    {
        sum.xx += v[i].xx;
        sum.yy += v[i].yy;
    }

    vector<ii> middle(4);
    middle[0].xx = sum.xx / m;
    middle[0].yy = sum.yy / m;
    middle[1].xx = sum.xx / m + 1;
    middle[1].yy = sum.yy / m;
    middle[2].xx = sum.xx / m;
    middle[2].yy = sum.yy / m + 1;
    middle[3].xx = sum.xx / m + 1;
    middle[3].yy = sum.yy / m + 1;

    vector<int> ans(4);
    for (int i = 0; i < m; i++)
    {
        ans[0] += calc(middle[0], v[i]);
        ans[1] += calc(middle[1], v[i]);
        ans[2] += calc(middle[2], v[i]);
        ans[3] += calc(middle[3], v[i]);
    }
    printf("%d\n", min({ ans[0], ans[1], ans[2], ans[3] }));
    
    return 0;
}

 

아악 빡쳐 또 틀렸대 ㅠ ㅠ ㅠ 뭐가 문제야

 

---

내가 푼 풀이의 문제점이 있었다.

 

나는 평균이 최솟값이라는 걸 가정하고 풀었는데 이게 답이라는 증명이 없다.

 

이렇게 가정하고 식을 세우는 걸 그리디라고 한다.

 

아무튼 증명이 없기 때문에 이게 맞다고 보긴 어렵고 최솟값은 중앙값으로 구할 수 있다.

 

 

 

 

증명은 이러하다

 

신기

 

중앙값이라 값을 하나 옮기면 숫자 개수의 차이가 생기니깐 그 차이만큼 거리값이 더해진다

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    vector<int> vx(m);
    vector<int> vy(m);
    for (int i = 0; i < m; i++)
        scanf("%d %d", &vx[i], &vy[i]);

    sort(all(vx));
    sort(all(vy));

    int midx, midy;
    if (m % 2 == 0)
    {
        midx = (vx[m / 2] + vx[m / 2 - 1]) / 2;
        midy = (vy[m / 2] + vy[m / 2 - 1]) / 2;
    }
    else
    {
        midx = vx[m / 2];
        midy = vy[m / 2];
    }

    int sum = 0;
    for (int i = 0; i < m; i++)
    {
        sum += abs(midx - vx[i]);
        sum += abs(midy - vy[i]);
    }
    printf("%d\n", sum);
    
    return 0;
}