백준(boj) 14889_스타트와 링크 (파이썬, c++)

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

풀이

---

짝수인 n명이 있는데 이들을 반으로 팀을 가른다(A팀, B팀) 그 뒤, 두명씩 짝지었을때 능력치는 어떤지 모두 더해주고 A팀 능력치와 B팀 능력치의 차이가 최소가 되는 값을 찾아준다.

player 배열을 만들어서 1 or 0을 부여해준다. 1은 A팀이고 0은 B팀이다.

cnt가 반절(n/2)을 넘어가면 팀설정이 잘못되었다. 끝내버린다.

pos가 마지막(n) 까지 탐색을 완료하였고, cnt가 반절(n/2)을 선택했으면 둘 씩 짝지어서 A팀, B팀 각각 계산을 해준다. 계산 해준 A팀과 B팀 능력치의 차이를 구해 반환한다.

python3

from sys import*
input = stdin.readline
def cal():
    teamA, teamB = 0, 0
    for i in range(n):
        for j in range(i+1, n):
            if player[i] and player[j]:
                teamA += a[i][j] + a[j][i]
            if not(player[i] or player[j]):
                teamB += a[i][j] + a[j][i]
    return abs(teamA - teamB)
def solve(pos, cnt):
    res = INF
    if cnt > n//2: return res
    if pos == n:
        if cnt == n//2: return cal()
        return res
    player[pos]=1
    res = min(res, solve(pos+1, cnt+1))
    player[pos]=0
    res = min(res, solve(pos+1, cnt))
    return res
INF=1e9
n=int(input())
a=[]; SUM=0
player=[0]*n
a=[list(map(int,input().split())) for _ in range(n)]
print(solve(0, 0))

C++

#include<cstdio>
#include<algorithm>
using namespace std;
const int INF = 1e9 + 1;
int n, a[20][20], player[20];
int cal(){
    int teamA=0, teamB=0;
    for(int i=0; i<n; i++){
        for(int j=i+1; j<n; j++){
            if(player[i] && player[j]) teamA += (a[i][j] + a[j][i]);
            if(!(player[i] || player[j])) teamB += (a[i][j] + a[j][i]);
        }
    }
    return abs(teamA - teamB);
}
int solve(int pos, int cnt){
    int res = INF;
    if (cnt > n/2) return res;
    if (pos == n){
        if(cnt == n/2) return cal();
        return res;
    }
    player[pos] = 1;
    res = min(res, solve(pos+1, cnt+1));
    player[pos] = 0;
    res = min(res, solve(pos+1, cnt));
    return res;
}
​
int main(){
    scanf("%d", &n);
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    printf("%d", solve(0, 0));
    return 0;
}

고찰

---

.