Suhwanc

문제 링크 : https://www.acmicpc.net/problem/15661

 

15661번: 링크와 스타트

첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

www.acmicpc.net

풀이

Brute force 문제 입니다!

이 문제는 선수들이 몇명씩 나뉘는지 모르기 때문에 순열로 풀 수 없고

팀을 두 개로 나눈 후 재귀호출을 통해서 선수들을 두 팀에 각각 집어 넣는 과정을 반복합니다.

이 때 재귀호출 함수의 인자로는 0~n까지 선수가 들어가는지에 대한 index와 두 팀의 선수들을 구성하는 vector를 반복해서 전달합니다.

 

소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int s[20][20];
int n;
int go(int index, vector<int> &first, vector<int> &second) {
    if (index == n) {
        if (first.size() == 0return -1;
        if (second.size() == 0return -1;
        int t1 = 0;
        int t2 = 0;
        for (int i=0; i<first.size(); i++) {
            for (int j=0; j<first.size(); j++) {
                if (i == j) continue;
                t1 += s[first[i]][first[j]];
            }
        }
        for (int i=0; i<second.size(); i++) {
            for (int j=0; j<second.size(); j++) {
                if (i == j) continue;
                t2 += s[second[i]][second[j]];
            }
        }
        int diff = t1-t2;
        if (diff < 0) diff = -diff;
        return diff;
    }
    int ans = -1;
    first.push_back(index);
    int t1 = go(index+1, first, second);
    if (ans == -1 || (t1 != -1 && ans > t1)) {
        ans = t1;
    }
    first.pop_back();
    second.push_back(index);
    int t2 = go(index+1, first, second);
    if (ans == -1 || (t2 != -1 && ans > t2)) {
        ans = t2;
    }
    second.pop_back();
    return ans;
}
int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> s[i][j];
        }
    }
    vector<int> first, second;
    cout << go(0, first, second) << '\n';
}
cs

코드 설명

go() 함수가 재귀호출 함수이며 first, second 로 팀을 나누었습니다.

이후 기저 사례로 index가 n일 때 각 팀 구성원이 1 이상이면 팀의 능력치를 구한 후 그 차이를 리턴합니다.

재귀 호출 과정에서는 first에 index 번 째 선수를 넣고 다시 go를 하고, 그 선수를 다시 pop하고 second에서 같은 과정을 반복하면서 선수들이 두 팀으로 나뉘는 모든 경우의 수를 호출하게끔 하였습니다.

 

 

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~

'백준 문제풀이' 카테고리의 다른 글

백준 15658번 연산자 끼워넣기 2  (0) 2020.01.20
백준 1248번 맞춰봐  (0) 2020.01.20
백준 9019번 DSLR  (0) 2020.01.20
백준 1697번 숨바꼭질  (0) 2020.01.16
백준 17404 RGB 거리 2  (0) 2020.01.16