반응형
14889번 스타트와 링크
1. 이해하기
- 전체 N명에서 N/2명으로 두 팀을 나눠서 각 팀의 선택된 사람들의 능력치 차이의 최소를 구하는 문제이다.
- 모든 경우를 다 해보는 완전탐색 문제.
2. 구현하기
-
N명에서 N/2을 고르는 방법을 만든다.
- 그 후 각 팀에서 고른 사람들의 능력치 차이의 최솟값을 반환한다.
int solve(int index, int cnt) { if(index > N) return MAX; if(index == N and cnt == N/2) { int sum1 = 0, sum2 = 0; for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) { if(i == j) continue; if(selected[i] and selected[j]) { sum1 += ability[i][j]; } else if(!selected[i] and !selected[j]) { sum2 += ability[i][j]; } } } return abs(sum1-sum2); } int ret = MAX; selected[index] = true; ret = min(ret,solve(index+1,cnt+1)); selected[index] = false; ret = min(ret,solve(index+1,cnt)); return ret; }
3. 전체 코드
#include <iostream>
using namespace std;
const int MAX = 987654321;
int ability[20][20];
bool selected[20];
int N;
int abs(int a) {
return (a<0)?-a:a;
}
int solve(int index, int cnt) {
if(index > N) return MAX;
if(index == N and cnt == N/2) {
int sum1 = 0, sum2 = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
if(i == j) continue;
if(selected[i] and selected[j]) {
sum1 += ability[i][j];
} else if(!selected[i] and !selected[j]) {
sum2 += ability[i][j];
}
}
}
return abs(sum1-sum2);
}
int ret = MAX;
selected[index] = true;
ret = min(ret,solve(index+1,cnt+1));
selected[index] = false;
ret = min(ret,solve(index+1,cnt));
return ret;
}
int main() {
cin >> N;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> ability[i][j];
}
}
cout << solve(0,0) << '\n';
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 14891번 톱니바퀴 (0) | 2019.10.06 |
---|---|
[백준] 14890번 경사로 (0) | 2019.10.05 |
[백준] 14888번 연산자 끼워넣기 (0) | 2019.10.04 |
[백준] 14503번 로봇 청소기 (0) | 2019.10.04 |
[백준] 14502번 연구소 (0) | 2019.10.03 |