14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
문제
백준문제이미지
풀이
N은 짝수이므로 항상 두팀으로 나누는게 보장된다.
따라서, N / 2는 1로 나머지 N / 2는 0으로 만들어 1팀과 0팀으로 나누고 sort를 해준뒤 순열을 사용하면 된다.
문제점
첫번째 팀은 첫번째 팀과 두번째 팀은 두번째 팀끼리 더해야 함을 주의
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < n; ++j)
{
cin >> a[i][j];
}
}
vector<int> b(n);
for (int i = 0; i < n / 2; ++i)
{
b[i] = 1;
}
sort(b.begin(), b.end());
int ans = 214748367;
do
{
vector<int> first, second;
for (int i = 0; i < n; ++i)
{
if (b[i] == 0)
{
first.push_back(i);
}
else
{
second.push_back(i);
}
}
int one = 0;
int two = 0;
for (int i = 0; i < n / 2; ++i)
{
for (int j = 0; j < n / 2; ++j)
{
if (i == j)
{
continue;
}
one += a[first[i]][first[j]];
two += a[second[i]][second[j]];
}
}
int diff = one - two;
if (diff < 0)
{
diff = -diff;
}
if (ans > diff)
{
ans = diff;
}
} while (next_permutation(b.begin(), b.end()));
cout << ans << "\n";
return 0;
}
결과
결과 이미지
pyo7410/Study
Contribute to pyo7410/Study development by creating an account on GitHub.
github.com
'알고리즘 > 백준' 카테고리의 다른 글
[Java] 백준 9095번 1, 2, 3 더하기 (0) | 2021.03.25 |
---|---|
[Java] 백준 2839번 설탕 배달 (0) | 2021.03.24 |
[C++] 백준 14888번 : 연산자 끼워넣기 (0) | 2020.05.30 |
[C++] 백준 1339번 : 단어 수학 (0) | 2020.05.30 |
[C++] 백준 2529번 : 부등호 (0) | 2020.05.30 |