#230205 일
어제에 이어(사실 어제자 벨로그를 1시간 전에 마무리해서 1시간 전에 이어..라고 해야 맞지만) 알고리즘 스터디 문제를 계속 풀어보겠다. 스포하자면 30분(스터디 시간 컷)만에 푸는데 성공해서 흥분한 내 자신을 볼 수 있다. (오예 울랄라울랄라)
1. 백준 14889번 스타트와 링크
<문제>
오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
N=4이고, S가 아래와 같은 경우를 살펴보자.
예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.
스타트 팀: S12 + S21 = 1 + 4 = 5
링크 팀: S34 + S43 = 2 + 5 = 7
1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.
스타트 팀: S13 + S31 = 2 + 7 = 9
링크 팀: S24 + S42 = 6 + 4 = 10
축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.
<입력>
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
<출력>
첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.
간단히 말하면 회사원 짝수 명에 대하여 반으로 팀을 쪼갰을 때, 능력치 차이가 최소인 경우를 찾으라는 것이다. 단, i와 j의 능력치는 ij능력치와 ji능력치의 합이며, ji능력치는 ij능력치와 수치가 다르다.
두 사람이 같이 묶여있는데 ji능력치와 ij능력치가 다르다는 게 상식적으로 말이 안 되므로, 사실 원하는 문제는 따로 있고 적절한 비유가 생각이 안 나서 사람이 하는 경기에 끼워맞췄다고 볼 수 있다..ㅎ 나같으면 귀찮아서 비유를 때려칠 텐데 어떻게든 실제 상황에 비유해서 내려고 하시는 걸 보면 출제자님이 대단하신 듯
하여튼 문제를 풀 때 마주한 첫 번째 문제는 바로 내가 조합을 코드로 짜본 적이 없다는 것이다. 능력치를 비교하려면 우선 n명의 회사원들을 두 팀으로 쪼개야 하는데, 그것조차 할 줄 몰라서 결국 못 풀고 집에 왔다. 스터디에서 c++에도 next_permutation 함수가 있다고 알려주셔서 메모를 해두긴 했다.
next_permutation함수를 공부해서 쓸지, 아니면 다른 방법을 쓸지 고민하다가.. 그냥 스터디 주제에 맞게 DFS로 조합을 구하기로 했다. DFS랑 친해지기 도전!
1) DFS로 두 팀으로 쪼개기 (조합)
void comb(int idx, int count, vector<int> c_array, vector<int> c2_array) {
if (count == team_num) {
for (int i = 1;i <= total_num;i++) {
if (visited[i]) c_array.push_back(i);
else c2_array.push_back(i);
}
calculate(c_array, c2_array);
c_array.clear();
c2_array.clear();
}
for (int i = idx; i <= total_num;i++) {
if (visited[i]) continue;
visited[i] = true;
comb(i, count + 1, c_array, c2_array);
visited[i] = false;
}
}comb가 입력받는 c_array와 c2_array는 빈 array이다. 한 가지 조합의 경우의 수가 구해질 때(count==team_num)마다 '조합을 구하면서 방문한 인덱스(조합에 포함된 인덱스)'들은 c_array에, <방문하지 않은(=조합에 넣지 않은) 인덱스들은 c2_array에 넣는다. 그리고 각 팀(c_array, c2_array)의 능력치를 구해주는 calculate 함수에 두 인자를 넘겨준다.
2) 각 경우의 수에 대하여 두 팀의 능력치의 차이 저장
void calculate(vector<int> c_array, vector<int> c2_array) {
int p1_sum=0;
for (int i = 0;i < c_array.size();i++) {
for (int j = 0;j < c_array.size();j++) {
int idx1 = c_array[i];
int idx2 = c_array[j];
p1_sum += a_array[idx1][idx2];
}
}
int p2_sum=0;
for (int i = 0;i < c2_array.size();i++) {
for (int j = 0;j < c2_array.size();j++) {
int idx1 = c2_array[i];
int idx2 = c2_array[j];
p2_sum += a_array[idx1][idx2];
}
}
int tmp;
if (p1_sum > p2_sum) {
tmp = p1_sum - p2_sum;
}
else {
tmp = p2_sum - p1_sum;
}
if (result_array.empty()) result_array.push_back(tmp);
else {
if (result_array[0] > tmp) {
result_array[0] = tmp;
}
}
}c1_array와 c2_array는 각 팀의 능력치가 아닌 팀원의 인덱스를 가지고 있는 array이다. 따라서 팀원의 능력치가 저장되어있는 a_array(ability array, main함수에서 생성된다)에서 능력치를 가져와 더한다. (각 팀의 전체 능력치 : p1_sum, p2_sum)
그리고 나서 p1_sum과 p2_sum의 차이를 계산한다.(tmp) tmp는 result_array에 저장된다. 만약 새롭게 구한 tmp가 result_array[0]보다 작으면 (result_array[0]은 tmp를 구하기 이전의 케이스들에 대하여 두 팀의 능력 차이값 중 가장 작은 값이다) result_array[0]의 값을 tmp로 갱신한다. main 함수에서는 가장 작은 차이값(result_array[0]을 최종적으로 출력한다.
메인 함수 포함 전체 코드 :
#include <iostream>
#include <vector>
using namespace std;
int total_num;
int team_num;
int a_array[21][21];
bool visited[21] = { false, };
vector<int> result_array;
int result;
void calculate(vector<int> c_array, vector<int> c2_array) {
int p1_sum=0;
for (int i = 0;i < c_array.size();i++) {
for (int j = 0;j < c_array.size();j++) {
int idx1 = c_array[i];
int idx2 = c_array[j];
p1_sum += a_array[idx1][idx2];
}
}
int p2_sum=0;
for (int i = 0;i < c2_array.size();i++) {
for (int j = 0;j < c2_array.size();j++) {
int idx1 = c2_array[i];
int idx2 = c2_array[j];
p2_sum += a_array[idx1][idx2];
}
}
int tmp;
if (p1_sum > p2_sum) {
tmp = p1_sum - p2_sum;
}
else {
tmp = p2_sum - p1_sum;
}
if (result_array.empty()) result_array.push_back(tmp);
else {
if (result_array[0] > tmp) {
result_array[0] = tmp;
}
}
}
void comb(int idx, int count, vector<int> c_array, vector<int> c2_array) {
if (count == team_num) {
for (int i = 1;i <= total_num;i++) {
if (visited[i]) c_array.push_back(i);
else c2_array.push_back(i);
}
calculate(c_array, c2_array);
c_array.clear();
c2_array.clear();
}
for (int i = idx; i <= total_num;i++) {
if (visited[i]) continue;
visited[i] = true;
comb(i, count + 1, c_array, c2_array);
visited[i] = false;
}
}
int main() {
cin >> total_num;
team_num = total_num / 2;
for (int i = 1;i <= total_num;i++) {
for (int j = 1;j <=total_num;j++) {
cin >> a_array[i][j];
}
}
vector<int> c_array;
vector<int> c2_array;
comb(1, 0, c_array, c2_array);
cout << result_array[0];
}와 나 30분만에 푼 거 실화임? 백준 가입하고 처음 있는 일입니다. 정화야 난 널 사랑해!!!!!!!!!!!!!1 넌 짱이야@!!!!!!!!!!!!
