푸키키키

문제 링크

• https://www.acmicpc.net/problem/15661

풀이

void makePossibleCase() {
  for(int depth=1;depth<=n/2;++depth) {
    dfs(0, 0, depth);
  }
}

void processing() {
  input();
  makePossibleCase();
  cout << ans << endl;
}

makePossibleCase();

문제를 해결하기 위해서 경우의 수를 만들어 내야한다. 경우의 수는 한팀이 2명이상이 되도록 팀을 구성해야 한다. 한 팀에 만약 2명을 배정해줬다면 나머지가 다 다른 팀으로 가게 되므로 다른 팀에 n-2가 배정된다. 이런식으로 3이면 n-3 ... 으로 한팀에 n/2까지만 할당한 경우까지 진행하면 풀어낼 수 있다.

아래는 depth≤n/2, 위는 depth<n이다. 눈에띄게 시간차이가 난다.

경우의 수 만들어내기 - dfs활용

bool visited[21];
void dfs(int depth, int nowidx, int maxDepth) {
  if(depth == maxDepth) {
    checkTeamScore();
    return;
  }

  for(int i=nowidx;i<n;++i) {
    if(visited[i] == false) {
      visited[i] = true;
      oneCase.push_back(i);
      dfs(depth+1, i+1, maxDepth);
      oneCase.pop_back();
      visited[i] = false;
    }
  }
}

• oneCase : 한 팀을 구성하는 index가 담길 vector

한팀에 배정할 팀원 수가 될 때까지 경우의 수를 만들어낸다. visited를 통해 이미 뽑아낸 것은 다시 뽑지 않도록 하고 nowidx를 통해 이미 뽑은 index보다 작은 값은 뽑지 않도록 해서 조합을 구현했다. 원하는 만큼 팀원을 뽑았다면 checkTeamScore()를 통해 답을 구해낸다.

checkTeamScore();

int ans = 999999;
void checkTeamScore() {
  leftTeamIdxClear();
  for(int j=0;j<oneCase.size();++j) {
    leftTeamIdx[oneCase[j]] = true;
  }
  ans = min(ans, calTeamScore());
}

왼쪽 팀에 배정된 인덱스들을 leftTeamIdx에 체크해준다. 이 값을 통해 왼쪽팀과 오른쪽 팀을 나누게 된다. 체크해준 후 calTeamScore()를 통해 두 팀의 각 값을 계산해내고 ans를 최신화해준다.

calTeamScore();

int calTeamScore() {
  int leftScore = 0;
  int rightScore = 0;
  for(int i=0;i<n;++i) {
    for(int j=i+1;j<n;++j) {
      if(leftTeamIdx[i] && leftTeamIdx[j]) {
        leftScore += table[i][j];  
      }
      if(!leftTeamIdx[i] && !leftTeamIdx[j]) {
        rightScore += table[i][j];  
      }
    }
  }

  return abs(leftScore - rightScore);
}

for문 두 개를 돌면서 두 인덱스가 모두 왼쪽 팀이면 그 값을 leftScore에, 둘다 오른쪽 팀이면 rightScore에 더하도록 했다. n제한이 20이므로 n^2 시간복잡도가 큰 부담이 없다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

/*
  인원수 달라도 됨
  1. 뽑는 경우의 수 생성
  2. 팀 만들어서 차이 보기
  - 반복
*/
int table[21][21];
int n;

void scorePreprocessing() {
  for(int i=0;i<n;++i) {
    for(int j=i+1;j<n;++j) {
      table[i][j] += table[j][i];
    }
  }
}

void input() {
  cin >> n;
  for(int i=0;i<n;++i) {
    for(int j=0;j<n;++j) {
      cin >> table[i][j];
    } 
  }
  scorePreprocessing();
}

vector<vector<int> > cases;
vector<int> oneCase;

bool leftTeamIdx[21];
void leftTeamIdxClear() {
  memset(leftTeamIdx, false, sizeof(leftTeamIdx));
}

int calTeamScore() {
  int leftScore = 0;
  int rightScore = 0;
  for(int i=0;i<n;++i) {
    for(int j=i+1;j<n;++j) {
      if(leftTeamIdx[i] && leftTeamIdx[j]) {
        leftScore += table[i][j];  
      }
      if(!leftTeamIdx[i] && !leftTeamIdx[j]) {
        rightScore += table[i][j];  
      }
    }
  }

  return abs(leftScore - rightScore);
}

int ans = 999999;
void checkTeamScore() {
  leftTeamIdxClear();
  for(int j=0;j<oneCase.size();++j) {
    leftTeamIdx[oneCase[j]] = true;
  }
  ans = min(ans, calTeamScore());
}

bool visited[21];
int recodeDepth = 0;
void dfs(int depth, int nowidx, int maxDepth) {
  if(depth == maxDepth) {
    if(recodeDepth != depth) {
      recodeDepth = depth;
    }
    checkTeamScore();
    return;
  }

  for(int i=nowidx;i<n;++i) {
    if(visited[i] == false) {
      visited[i] = true;
      oneCase.push_back(i);
      dfs(depth+1, i+1, maxDepth);
      oneCase.pop_back();
      visited[i] = false;
    }
  }
}

void makePossibleCase() {
  for(int depth=1;depth<=n/2;++depth) {
    dfs(0, 0, depth);
  }
}

void processing() {
  input();
  makePossibleCase();
  cout << ans << endl;
}

int main() {
  processing();
}