반응형
https://www.acmicpc.net/problem/14889
14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
[ 문제풀이 ]
팀의 조합을 $_{N}\textrm{C}_{\frac{N}{2}}$로 뽑아 같은 팀끼리의 점수를 더해 각 값의 차를 ans에 갱신해주는 방법을 사용했습니다.
1. $\frac{N}{2}$명을 뽑아 팀을 만듭니다.
2. 같은 팀끼리 점수를 더해 각 값의 차를 ans에 갱신해줍니다.
3. 가장 낮은 ans의 값을 출력해줍니다.
[ 소스 코드 ]
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 | #include<iostream> using namespace std; int N; int arr[20][20]; int box[20]; int ans = 987654321; void dfs(int level, int n) { if (level == N / 2) { int a, b; a = b = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { //같은 팀이면 값 더하기 if (box[i] == 1 && box[j] == 1) { a += arr[i][j]; } else if (box[i] == 0 && box[j] == 0) { b += arr[i][j]; } } } ans = min(ans, abs(a - b)); return; } for (int i = n; i < N; i++) { //20 C 10 box[i] = 1; dfs(level + 1, i + 1); box[i] = 0; } } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { scanf("%d", &arr[i][j]); } } dfs(0, 0); printf("%d", ans); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 1931번 - 회의실 배정 (C++) (0) | 2022.08.20 |
|---|---|
| [ 백준 ] 11047번 - 동전 0 (C++) (0) | 2022.08.19 |
| [ 백준 ] 11727번 - 2xn 타일링 2 (C++) (0) | 2022.08.17 |
| [ 백준 ] 14499번 - 주사위 굴리기 (C++) (0) | 2022.08.16 |
| [ 백준 ] 3190번 - 뱀 (C++) (0) | 2022.08.15 |