글 읽기 - 그냥 N^2로 탐색하는게 왜 틀린건가요?

mym0404 3년 전 0

좌표 압축은 안해도 그냥 특정 소가 있는 지점으로 x,y를 한칸씩 옮겨가며

한 소의 지점마다 4번씩 모두 검사해서 O(N^2)로 통과를 할수있다고 생각했는데(소좌표는 모두 홀수이고 선 좌표는 짝수기 때문에 겹치는 일 없이)

WA가 나는 이유는 무엇일까요?

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define endl "\n"
#define pb push_back
#define all(X) (X).begin(), (X).end()
#define sz(X) (int)(X).size()
#define fi first
#define se second

void solve() {
   int N;
   cin >> N;
   vector<pi> cows;
   for (int i = 0; i < N; i++) {
      int x, y;
      cin >> x >> y;
      cows.pb({x, y});
   }
   int ans = N;
   for (int i = 0; i < N; i++) {
      pi cur = cows[i];

      assert(cur.fi % 2 == 1);
      assert(cur.se % 2 == 1);

      vector<pi> p = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
      for (auto parity: p) {
         int a = cur.fi + parity.fi;
         int b = cur.se + parity.se;
         if (a == 0 || b == 0 || a == 1000000 || b == 1000000)
            continue;
         int c1 = 0, c2 = 0, c3 = 0, c4 = 0;
         for (pi cow: cows) {
            if (cow.fi < a && cow.se < b)
               c1++;
            else if (cow.fi < a && cow.se > b)
               c2++;
            else if (cow.fi > a && cow.se < b)
               c3++;
            else if (cow.fi > a && cow.se > b)
               c4++;
         }
         assert(c1 + c2 + c3 + c4 == N);
         ans = min(ans, max(c1, max(c2, max(c3, c4))));
      }
   }
   cout << ans;
}

int main() {
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   solve();
   return 0;
}

snrnsidy 3년 전 1

소를 기준으로 사분면 나눠서 구해주면 최적의 답을 구할 수 없습니다

예를 들어, 데이터 조건은 무시하고 (-1,0),(0,1),(0,-1),(1,0) 이렇게 4개의 좌표가 있을 때 어떻게 될까요?

mym0404 3년 전 0

@snrnsidy

아.. 새벽인데 빠른 답변 감사합니다!

mym0404 3년 전 0

그런데 다시 생각해보니 데이터에 소는 모두 홀수이고 a, b는 짝수여서 제가 코드를 저렇게 짠건데 그러면 소와 선분이 겹칠일이 없어서 4방향을 그냥 갈라도 되지 않나요?

mym0404 3년 전 0

@snrnsidy 그리고 소들의 좌표를 기준으로 좌표값압축해서 푸는것이 결국 소를 기준으로 사분면을 나누는것이 아닌가요?

snrnsidy 3년 전 1

공유해주신 코드를 보면 각 소의 좌표에 대해서 4방향을 본 다음 각각에 대해서 사분면 만들어서 계산하는 걸로 이해했습니다.

제가 전에 풀었을 때 위 방법으로 했다가 어떤 케이스에 걸려서 다른 방법을 생각했던 기억이 나네요.

그 케이스가 어떠한 케이스인지는 잘 모르겠습니다

index 3년 전 2

소 주변이 아닌 다른 장소를 기준으로 나눠야 최적이 되는 경우가 생기더라고요

mym0404 3년 전 0

아 이제 이해됐습니다 감사합니다!

mym0404 3년 전 0

참고로 index 님이 주신 반례는 큰 가장자리 네모로 소들이 배치되어있을때 정 중앙 점이 답을 이미하는 (a,b) 가 되는 것입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

그냥 N^2로 탐색하는게 왜 틀린건가요?

mym0404 3년 전 0

snrnsidy 3년 전 1

mym0404 3년 전 0

mym0404 3년 전 0

mym0404 3년 전 0

snrnsidy 3년 전 1

index 3년 전 2

mym0404 3년 전 0

mym0404 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말