백준 14889 C++

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

14889번: 스타트와 링크

 

문제 정리

팀의 능력치 : 팀에 속한 모든 쌍의 능력치 Sij의 합 = Sij + Sji
두 팀의 능력치 차이의 최솟값을 구하기

 

생각

모든 경우의 수를 구해야 하긴 하는데…

1. 팀 구성 방식 - 중복이 허용되지 않으니까 순열로 구해야 하긴 함! 한 팀에 속하면 visited로 방문 표시를 하면서 방문한 팀이 n/2될 때 까지 방문하고! 이런 식
2. 팀의 능력치 비교 - 표에서 그대로 가져오는데 두 팀의 능력치 차를 구한 후 절댓값을 해준 후 ans에 저장해둠

 

코드

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

int n, ans = -1;
int board[21][21];
bool visited[21];

void dfs(int depth, int count) {
    if (depth == n / 2) {
        int team1 = 0, team2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i] && visited[j]) {
                    team1 += board[i][j];
                } else if (!visited[i] && !visited[j]) {
                    team2 += board[i][j];
                }
            }
        }
        int temp_ans = abs(team1 - team2);
        if (ans == -1 || temp_ans < ans)
            ans = temp_ans;
    }

    for (int i = count; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(depth + 1, i + 1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    dfs(0, 0);
    cout << ans;
}

dfs로 풀었다

 

- 팀 나누기

  for (int i = count; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(depth + 1, i + 1);
            visited[i] = false;

한 팀에 속하면 visited로 방문 표시를 한다!

방문 표시 후 재귀로 계속 호출했다 

호출 하다가 depth == n/2가 되면 그 때 팀이 다 나눠진 것 이므로 능력치를 더해준다!

 

- 팀 능력치 더하기

    if (depth == n / 2) {
        int team1 = 0, team2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i] && visited[j]) {
                    team1 += board[i][j];
                } else if (!visited[i] && !visited[j]) {
                    team2 += board[i][j];

visited로 팀을 구별해서 능력치를 더해준다

 

- 최소 능력치 차이 값 계산하고 갱신하기

// int ans = -1;
 
        int temp_ans = abs(team1 - team2);
        if (ans == -1 || temp_ans < ans)
            ans = temp_ans;

두 팀의 능력치를 뺀 값에 절댓값을 취해준다.

ans는 전역에 -1이라 정의해뒀기 때문에 처음 값을 저장하는 경우를 if로 조건을 추가해줬다!

이후에는 최솟값만 갱신되도록!

 

아 그리고 이것도 벡터로 풀려고 했는데 dfs bfs는 배열로 푸는게 익숙해서 다시 배열 사랑러로 돌아왔다 하하

벡터가 편한가?

---

 

약간 알고리즘 권태기 알태기... 왔었는데 요즘엔 푸는 게 재밌다!

다행이군