(C++) - 백준(BOJ) 6987 : 월드컵

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

6987번: 월드컵

전수조사 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

받은 결과 2차원 배열 result, 만들 결과 이차원 배열 madeResult, round별 home, away team들이 저장될 vector vs를 선언해줍니다. 매 round별 두 team이 대결하므로 6개의 팀 중 2개를 조합으로 구성해 vs에 저장해줍니다.

📔 풀이과정

매 test case마다 dfs함수를 수행합니다.

매 round별 home, away team은 3가지 결과를 가질 수 있습니다.

1. home 승, away 패

2. home 패, away 승

3. home 무, away 무

매 round별 3가지 상태에 대해 madeResult에 반영 후 재귀적으로 함수를 호출해줍니다. 각 상태별 함수 실행이 끝난 뒤에는 원복해줘야합니다.

 

기저는 round가 끝난 시점이며 madeResult와 result가 같은지 비교해줍니다.

총 round는 15이므로 시간복잡도는 3^15가 됩니다.

📔 정답출력

dfs함수 결과를 매 test case마다 형식에 맞게 출력해줍니다.

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

struct VS{
  int home, away;
};

int result[10][10], madeResult[10][10];
vector <VS> vs;

int dfs(int played){
  if(played == 15){
    for(int i = 0; i < 6; i++){
      for(int j = 0; j < 3; j++){
        if(result[i][j] != madeResult[i][j]) return 0;
      }
    }
    return 1;
  }

  int ans = 0;
  int home = vs[played].home;
  int away = vs[played].away;
  //승패
  madeResult[home][0]++; madeResult[away][2]++;
  ans = max(ans,dfs(played + 1));
  madeResult[home][0]--; madeResult[away][2]--;

  //패승
  madeResult[away][0]++; madeResult[home][2]++;
  ans = max(ans,dfs(played + 1));
  madeResult[away][0]--; madeResult[home][2]--;

  //무무
  madeResult[away][1]++; madeResult[home][1]++;
  ans = max(ans,dfs(played + 1));
  madeResult[away][1]--; madeResult[home][1]--;

  return ans;
}

int main(){
  fastio;
  for(int i = 0; i < 6; i++){
    for(int j = i + 1; j < 6; j++){
      vs.push_back({i,j});
    }
  }
  for(int t = 0; t < 4; t++){
    memset(madeResult,0,sizeof(madeResult));
    for(int i = 0; i < 6; i++){
      for(int j = 0; j < 3; j++){
        cin >> result[i][j];
      }
    }
    cout << dfs(0) << ' ';
  }
}

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.