백준 2503. 숫자 야구

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

2503번: 숫자 야구

 

이 문제는 

 

1. 1~9까지의 숫자중 3개의 조합을 뽑는다.

ex) 123, 124, 125 ...

 

2. 뽑은 3개의 조합수의 모든 순열을 구한다.

ex) 뽑은 조합수가 123이라면 123, 132, 213 ...

 

3. 순열을 영수가 물어본 모든 숫자들을 비교해서 스트라이크와 볼의 숫자가 일치하는지 판별한다.

영수가 물어본 모든 숫자들에 대해 스트라이크와 볼수가 일치한다면 그 순열이 영수가 생각하고 있을 가능성이 있는 숫자이다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int n;
int res = 0;
int nums[9] = {1,2,3,4,5,6,7,8,9};
int nums_idx[9] = {1,1,1,0,};
vector<int> comb;

vector<string> asked;
vector<pair<int,int>> sb;

// _v는 영수가 물어본 숫자들에대해 대입해볼 조합수
bool Calculate(vector<int> _v) {
    for(int i = 0; i < n; i++) {
        int strike = 0, ball = 0;

        // strike, ball 판별
        for(int j = 0; j < 3; j++) {
            for(int k = 0; k < 3; k++) {
                // 영호가 물어본 숫자의 각자리와 조합수의 자리를 비교해서 strike,ball 판별
                if(_v[j] == asked[i][k]-'0') {
                    // 같은 자리라면 스트라이크
                    if(j == k)
                        strike++;
                    else
                        ball++;
                    break; // 모든 숫자들은 서로 다르므로 strike나 ball을 찾았다면 더이상 탐색 안해도됨
                }
            }
        }

        // 영수가 물어본 숫자들중 하나라도 현재 대입해본 조합수와 strike,ball수가 맞지않으면
        // 그 수는 영수가 생각하고있을 가능성이 있는 수가 될수 없음
        if((sb[i].first != strike) || (sb[i].second != ball)) {
            return false;
        }
    }
    // 모든 조건을 통과했다면 _v는 영수가 생각할고 있을 가능성이 있는 숫자임
    return true;
}


int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        string number;
        cin >> number;
        asked.push_back(number);

        int s, b;
        cin >> s >> b;
        sb.push_back({s,b});
    }

    do {
        // 숫자 조합 만들기
        for(int i = 0; i < 9; i++) {
            if(nums_idx[i] == 1) {
                comb.push_back(nums[i]);
            }
        }

        // 만들어진 조합수에 대하여 모든 순열을 구해서
        // 그 숫자가 영수가 생각하고있을 가능성이 있는 숫자인지 판별함
        do {
            if(Calculate(comb))
                res++;
        } while(next_permutation(comb.begin(), comb.end()));

        comb.clear();
    } while(prev_permutation(nums_idx, nums_idx+9));

    cout << res;
}