2503번: 숫자 야구
첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.
www.acmicpc.net
- 가능한 모든 경우의 수에서 소거해나가기
/* 1. ball은 strike를 제외한 경우를 생각할 것 */
/* 2. 문제 잘 읽기 -> 서로 다른 수를 힌트로 제공 */
#include <iostream>
#include <string>
#include <queue>
#include <string.h>
using namespace std;
int N;
queue<string> q;
string hint, candidate;
int strikes, balls;
bool vst[10];
void bf() {
if (candidate.size() == 3) {
q.push(candidate);
return;
}
for (int i = 1; i <= 9; ++i) {
if (vst[i]) continue;
vst[i] = true; /* 2 */
candidate.push_back(i + '0');
bf();
candidate.pop_back();
vst[i] = false; /* 2 */
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
bf();
while (N--) { // 숫자를 듣기
cin >> hint >> strikes >> balls;
memset(vst, 0, sizeof(vst));
for (auto digit : hint) {
vst[digit - '0'] = true;
}
int qs = q.size();
while (qs--) { // 후보를 살피기
string candidate = q.front();
q.pop();
// strikes
int ctr = 0;
for (int i = 0; i < 3; ++i) {
if (hint[i] == candidate[i]) {
++ctr;
}
}
if (strikes != ctr) continue;
// balls
ctr = 0;
for (int i = 0; i < 3; ++i) {
if (vst[candidate[i] - '0'] && hint[i] != candidate[i]) { /* 1 */
++ctr;
}
}
if (balls != ctr) {
continue;
}
q.push(candidate);
}
}
cout << q.size();
return 0;
}