백준 2503번 숫자 야구

문제 링크입니다: https://www.acmicpc.net/problem/2503

1~9까지의 숫자 중 3개를 뽑아서 만들 수 있는 조합을 모두 만들어보며 조건을 충족하는지 확인하면 되는 브루트 포스(Brute Force) 문제였습니다.

next_permutation만 잘 쓴다면 쉽게 풀 수 있는 문제였습니다.

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

 

int N;

vector<pair<string, pair<int, int>>> v;

 

bool successful(vector<int> &temp)

{

        bool flag = true;

        for (int i = 0; i < v.size(); i++)

        {

                 int s = 0, b = 0;

                 for(int j=0; j<temp.size(); j++)

                         for (int k = 0; k < 3; k++)

                         {

                                 if (temp[j] == (v[i].first[k] - '0'))

                                 {

                                          if (j == k)

                                                  s++;

                                          else

                                                  b++;

                                          break;

                                 }

                         }

                 if ((s != v[i].second.first) || (b != v[i].second.second))

                 {

                         flag = false;

                         break;

                 }

        }

        return flag;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

        for (int i = 0; i < N; i++)

        {

                 string num;

                 int s, b;

                 cin >> num >> s >> b;

 

                 v.push_back({ num, {s, b} });

        }

 

        long long result = 0;

        //모든 조합을 시도해보며

        for (int i = 1; i <= 9; i++)

        {

                 vector<int> baseball;

                 baseball.push_back(i);

                 for (int j = i + 1; j <= 9; j++)

                 {

                         baseball.push_back(j);

                         for (int k = j + 1; k <= 9; k++)

                         {

                                 baseball.push_back(k);

                                 do

                                 {

                                          //조건을 충족하는지 확인

                                          if (successful(baseball))

                                                  result++;

                                 } while (next_permutation(baseball.begin(), baseball.end()));

                                 baseball.pop_back();

                         }

                         baseball.pop_back();

                 }

                 baseball.pop_back();

        }

        cout << result << "\n";

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~