[C++] 백준 14889 : 스타트와 링크
#include <iostream>
#include <algorithm> // min
#include <vector>
#include <cmath> // abs(절댓값)
using namespace std;
int map[21][21]; // 세로 i, 가로 j
bool visited[21]; // 방문 여부
int N;
int Min = 999999999;
void DFS(int num, int cnt){
if(cnt == N / 2){
// 팀 저장 - 지역변수로 해야 별도의 초기화 불필요, 모든 수열에 따라 다른 팀 저장
vector<int> team1;
vector<int> team2;
// 팀 별 능력치 저장
int tmp1 = 0;
int tmp2 = 0;
for(int i = 1; i <= N; i++){ // 팀 저장
if(visited[i]){ // 골라진 수열의 수
team1.push_back(i); // team1에 저장
} else {
team2.push_back(i); // team2에 저장
}
}
for(int i = 0; i < N/2; i++){
// printf("team1 : %d team2 : %d\n", team1[i], team2[i]);
for(int j = i; j < N/2; j++){
tmp1 += map[team1[i]][team1[j]] + map[team1[j]][team1[i]];
tmp2 += map[team2[i]][team2[j]] + map[team2[j]][team2[i]];
}
}
int tmp = abs(tmp1 - tmp2);
// printf("tmp : %d tmp1 : %d tmp2 : %d\n", tmp, tmp1, tmp2);
Min = min(Min, tmp);
return;
}
for(int i = num; i <= N; i++){
visited[i] = true; // visited면 순열 골라진 것
DFS(i+1, cnt + 1);
visited[i] = false;
}
}
int main(int argc, char** argv){
scanf("%d", &N);
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
scanf("%d", &map[i][j]); // 능력치 표 입력받기
}
}
visited[1] = true;
DFS(2, 1); // 2번부터 체크, 1은 이미 팀 1에 속해있다고 가정
printf("%d", Min);
return 0;
}
-
팀을 짜기 위해서는 팀에 속할 2/N명의 사람을 고르면 된다. 따라서 순열과 같다. 1~N까지의 수 중에서 2/N개를 구하는 것과 같다. 순열을 구할때는 백트래킹을 이용해서 구한다. 팀의 순서는 중요하지 않으므로 1번은 이미 팀에 속해있다고 보고 다음 값부터 구해주었다.
-
골라진 순열의 값은 visited에 true로 체크되어 있는 것이 골라진 수이다. 따라서 반복문을 돌면서 각각의 팀을 저장해준다. 동적 할당 배열이 필요하기 때문에 vector를 사용하여 팀을 저장하였다.
-
팀이 (1, 2, 4) (3, 5, 6) 이렇게 나누어졌다고 했을 때 (1, 2, 4)의 능력치를 구하려면 (1, 2), (1, 4), (2, 4) 이렇게 세 가지를 구해주어야한다. 때문에 2중 for문을 이용해 모든 경우를 탐색해주어야한다.
-
절댓값을 구할때는 STL 라이브러리 cmath의 abs를 사용한다.
Author And Source
이 문제에 관하여([C++] 백준 14889 : 스타트와 링크), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-14889-스타트와-링크저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)