[Baekjoon] 14889번 스타트와 링크.cpp
어렵게 생각하면 어렵지만 쉽게 생각하면 쉬운 문제다.. ?
문제에서 두 팀으로 사람을 나누는 작업에서 첫 번째 조합, 그리고 나뉜 팀에서 능력치를 더하기 위해 두 명씩 나누는 두 번째 조합, 이렇게 두 번의 dfs를 돌려야 할 것으로 생각했다. 그렇게 된다면 스택의 크기가 너무 커진다.
하지만 다행히도 이번 문제는 팀을 나누는 것만 dfs로 해주고 능력치 합은 완전탐색으로 해주어도 시간 초과가 나지 않는다.
필자는 팀을 나누는 용도로 joined
라는 배열을 만들고 true
라면 A팀, false
라면 B팀에 분류하는 식으로 구분하였다. 따라서 joined
의 n개의 원소 중 n / 2
개를 선별하였다면 완전탐색을 통해 같은 팀원일 때의 능력치만 합산해주는 식으로 처리하여 정답을 받았다.
물론 시간이 아슬아슬하게 통과된 것으로 보이지만, 가장 간단한 코드가 아닐까 싶다..
#include <iostream>
#include <math.h>
int n;
int ability[20][20];
bool joined[20];
int min = 1000000000;
void member_list_up(int memberNum, int pos){
if(memberNum == n / 2){
int start = 0, link = 0;
for(int mem1 = 0; mem1 < n; mem1++){
for(int mem2 = 0; mem2 < n; mem2++){
if(joined[mem1] && joined[mem2]){
start += ability[mem1][mem2];
}
if(!joined[mem1] && !joined[mem2]){
link += ability[mem1][mem2];
}
}
}
int result = std::abs(start - link);
if(result < min){
min = result;
}
}
else{
for(int count = pos; count < n; count++){
joined[count] = true;
member_list_up(memberNum + 1, count + 1);
joined[count] = false;
}
}
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
std::cin >> n;
for(int row = 0; row < n; row++){
for(int col = 0; col < n; col++){
std::cin >> ability[row][col];
}
}
member_list_up(0, 0);
std::cout << min;
}
Author And Source
이 문제에 관하여([Baekjoon] 14889번 스타트와 링크.cpp), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@cedongne/Baekjoon-14889번-스타트와-링크.cpp저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)