[KOI] 백준 2503 - 숫자 야구

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

체크리스트

서로 다른 숫자 세 개로 구성된 세 자릿수

 

세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번

 

다른 자리에 위치하면 볼 한 번

풀이

수가 단 3자리에 1부터 9까지 이므로 3자리 숫자를 모두 검색하는 완전 탐색을 생각해볼 수 있다. 이때 "서로 다른 숫자 세 개"라는 조건에 유의하여 같은 숫자가 있으면 건너뛰도록 한다.

 

어떤 수 조합이 후보에 포함될 수 있으려면 N개의 질의에 대해 스트라이크와 볼 개수가 일치해야 한다. 하나라도 그렇지 않으면 모순이 발생한 것이므로 생각할 수 있는 조합이 될 수 없다.

 

모든 수 조합에 대해 N개의 질의를 만족하는 횟수를 구하면 정답을 받을 수 있다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n;
int query[100][3];
 
void solve()
{
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    cin >> query[i][0] >> query[i][1] >> query[i][2];
  }
 
  int ans = 0;
 
  for (int i = 1; i < 10; i++)
  {
    for (int j = 1; j < 10; j++)
    {
      for (int k = 1; k < 10; k++)
      {
        bool nice = true;
 
        if (i == j or j == k or i == k) continue;
 
        for (int s = 0; s < n; s++)
        {
          int strike = 0, ball = 0;
 
          int a = query[s][0] / 100;
          int b = query[s][0] / 10 % 10;
          int c = query[s][0] % 10;
 
          strike += a == i;
          strike += b == j;
          strike += c == k;
 
          ball += a == j or a == k;
          ball += b == i or b == k;
          ball += c == i or c == j;
 
          nice &= (strike == query[s][1] and ball == query[s][2]);
          
          if (nice and strike == 3)
          {
            cout << 1;
            return;
          }
        }
 
        ans += nice;
      }
    }
  }
 
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록