6987 c++ - 월드컵

어떻게 풀까 고민하다가. 데이터가 적어서 그냥 조합으로 풀었습니다. 

[C++] 순열, 조합

가능한 모든 조합을 combi로 찾아서 matches 를 만들고, 해당 matches부터 재귀적으로 찾아 모든 게임이 끝났을때 result의 승,무,패가 0이 아닌경우를 찾아서 반환하는 경우로 처리하였습니다.

 

#include <iostream>
#include <vector>
 
using namespace std;
 
vector<pair<int, int>> matches;
 
bool isValid(vector<vector<int>>& results, int matchIdx) {
  if (matchIdx == 15) {
    for (int i = 0; i < 6; i++) {
      if (results[i][0] != 0 || results[i][1] != 0 || results[i][2] != 0)
        return false;
    }
    return true;
  }
 
  int teamA = matches[matchIdx].first;
  int teamB = matches[matchIdx].second;
 
  if (results[teamA][0] > 0 && results[teamB][2] > 0) {
    results[teamA][0]--;
    results[teamB][2]--;
    if (isValid(results, matchIdx + 1)) return true;
    results[teamA][0]++;
    results[teamB][2]++;
  }
 
  if (results[teamA][1] > 0 && results[teamB][1] > 0) {
    results[teamA][1]--;
    results[teamB][1]--;
    if (isValid(results, matchIdx + 1)) return true;
    results[teamA][1]++;
    results[teamB][1]++;
  }
 
  if (results[teamA][2] > 0 && results[teamB][0] > 0) {
    results[teamA][2]--;
    results[teamB][0]--;
    if (isValid(results, matchIdx + 1)) return true;
    results[teamA][2]++;
    results[teamB][0]++;
  }
 
  return false;
}
 
void combi(int n, int r, int* arr, int start, vector<int> v) {
  if (v.size() == r) {
    matches.push_back({v[0], v[1]});
    return;
  }
 
  for (int i = start + 1; i < n; i++) {
    v.push_back(arr[i]);
    combi(n, r, arr, i, v);
    v.pop_back();
  }
}
 
int main() {
  vector<vector<int>> allGames(4, vector<int>(18));
 
  for (int i = 0; i < 4; i++) {
    for (int j = 0; j < 18; j++) {
      cin >> allGames[i][j];
    }
  }
 
  int arr[] = {0, 1, 2, 3, 4, 5};
  vector<int> temp;
  combi(6, 2, arr, -1, temp);
 
  for (int i = 0; i < 4; i++) {
    vector<vector<int>> eachGames(6, vector<int>(3));
    for (int j = 0; j < 6; j++) {
      eachGames[j][0] = allGames[i][j * 3];
      eachGames[j][1] = allGames[i][j * 3 + 1];
      eachGames[j][2] = allGames[i][j * 3 + 2];
    }
 
    if (isValid(eachGames, 0))
      cout << "1 ";
    else
      cout << "0 ";
  }
 
  return 0;
}