백준 14889 스타트와 링크

skyepodium·2019년 7월 23일

백준14889 백트래킹 비트마스킹 순열 스타트와링크

sw 역량 테스트

목록 보기

3/12

팀 나눌때 항상 이 짤 생각나서

문제

두 팀 총 힘의 차이의 최소값을 구하는 문제

n 총 인원수 (4 ≤ n ≤ 20, n은 짝수)
한 팀의 힘은 다음과 같이 계산
한 팀에 1, 3, 5가 속했을때 2명씩 추출한다.
팀 총합 = s[1][3] + s[3][1] + s[1][5] + s[5][1] + s[3][5] + s[5][3]
두팀의 총 힘 차이의 최소값을 구하세요
예시

1) 스타트 팀 1, 2가 속하고 링크 팀 3, 4 일때

스타트팀 총 힘의 합 = s[1][2] + s[2][1] = 1 + 4 = 5
링크팀 총 힘의 합 = s[3][4] + s[4][3] = 2 + 5 = 7

2) 스타트 팀 1, 3가 속하고 링크 팀 2, 4 일때

스타트팀 총 힘의 합 = s[1][3] + s[3][1] = 2+ 7 = 9
링크팀 총 힘의 합 = s[2][4] + s[4][2] = 6 + 4 = 10

따라서, 힘 차이 최소값은 1

시간 제한 2초
문제 링크

풀이 과정

1. 문제 분해

문제를 3개의 작은 문제로 나눠 봅시다.

1) n명을 n/2명으로 구성된 2개의 팀으로 나누고
2) 각 팀 두명씩 추출해서 힘을 계산하고
3) 두 팀 총 힘의 차이의 최소값을 구하는 문제

정리해보면,

1) n명을 n/2로 2개로 쪼갭니다.
2) 2중 for문으로 중복되지 않게, 2명씩 추출합니다.
3) 각 팀의 총 힘을 구하고, 뺄셈해줍니다.

2), 3)은 노멀한 계산입니다.
중요한것은 1) 어떻게 n명을 n/2로 구성된 2개의 팀으로 나눌 것인가요?

여러 가지방법이 있고, 제가 아는 방법은 3가지 입니다.

재귀(백트래킹 이라고도 하고, 탐색 방법이 DFS와 유사해서, DFS라고도 부릅니다.)
순열
비트마스킹

까짓거 다해봅시다.

2. n명을 n/2로 구성된 2개의 팀으로 나누기

1) 재귀

1~n번 사람에 대해서, 스타트팀에 들어가거나, 링크팀에 들어가거나를 결정해줍니다.

시간복잡도는 O(2^n)
n이 20이하일 경우에만 사용가능합니다.

재귀가 스택을 이용하기 때문에 그 이상 넘어가면 터져버릴지도 몰라요

void go(int idx){
    // 재귀이기 때문에 종료 처리를 잘 해줘야합니다.
  	if(idx == n + 1){
      if(start.size() == n/2 && link.size() == n/2){
        // 여기서 다음 계산을 진행합니다.
      }
      // return으로 종료 필수!
      return;
    }
  
    // idx선수에 대해 두가지 케이스가 존재한다.
    // 1) 스타트 팀에 넣는다.
    start.push_back(idx);
    go(idx + 1);
    start.pop_back();
    
    // 2) 링크 팀에 넣는다.
    link.push_back(idx);
    go(idx + 1);
    link.pop_back();
}

2) 순열

만약 00001111이 들어있는 배열이 있을때 다음 순열은 무엇일까요?
00010111

그 다음은?
00011011

0이 들어있는 사람은 스타트팀, 1이 들어있는 사람은 링크팀으로 넣어줍니다.

정리하면, n명일때 n/2를 선택하는 모든 경우는
길이가 n이고 0이 (n-n/2)개, 1이 (n-n/2)개 들어있는 순열을 제일 처음부터 끝까지 만들어 주면됩니다.

// 순열을 저장할 리스트 v를 벡터로 생성합니다.
vector<int> v;
// next_permutation을 사용하기 때문에
// 0을 먼저 넣어주고, 1을 다음으로 채워줍니다.
for(int i=0; i<n/2; i++) v.push_back(0);
for(int i=0; i<n/2; i++) v.push_back(1);

do{
    //스타트팀, 링크팀을 만들고
  	vector<int> start, link;
	for(int i=0; i<(int)v.size(); i++){
      if(v[i] == 0){
        // 0일때 스타트팀에 넣어줍니다.
        start.push_back(i+1);
      }
      else{
        // 1일때 링크팀에 넣어줍니다.
        link.push_back(i+1);
      }
    }

  	// 여기서 다음 계산을 진행해줍니다.

}while(next_permutation(v.begin(), v.end()));

3) 비트 마스킹

순열이 사용했던 방법과 유사합니다.

n이 8일때
00001111을 2진수로 바꾸면 15
11110000을 2진수로 바꾸면 240

15부터 240까지 반복문을 돌면서 0이 들어있는 사람은 스타트팀, 1이 들어있는 사람은 링크팀으로 넣어줍니다.

for(int i=(1 << (n/2 + 1)) - 1; i < (1 << n); i++){
	vector<int> start, link;
  
  	// n개의 비트에 대해 검사
	for(int j=0; j < n; j++){
        // 1) 해당 비트가 0 이면 스타트팀에 넣고
		if((i & (1 << j)) != 0) start.push_back(j+1);
      	// 2) 해당 비트가 1이면 링크팀에 넣습니다.
        else link.push_back(j+1);
    }
}

코드

1) 재귀

#include <iostream>
#include <vector>
#define max_int 21
/*
최소값 구할때 제일 큰값으로 초기화하는데
얼마인지 계산하기 귀찮을때, 단, 변수의 최대 크기가 int범위 안에 들어올때
2147483647 로 초기화 합니다.
 
리듬감 있게 외우면 20초 이내에 외워집니다.
 이일~ 사칠사팔~ 삼육사칠~
 */
#define max_val 2147483647
using namespace std;

/*
 시간 복잡도: O(2^n*n^2)
 공간 복잡도: O(n^2)
 사용한 알고리즘: 재귀(DFS)
 사용한 자료구조: 배열, 리스트
 */

int n, a[max_int][max_int], start_sum, link_sum, start_first, start_second, link_first, link_second, result = max_val;

// 스타트, 링크 팀에 속한 사람들의 번호를 저장할 리스트를 벡터로 생성
vector<int> start, link;

// 최소값 반환
int min(int a, int b){
    return a < b ? a : b;
}

// 절대값 반환
int abs(int a){
    if(a < 0) a = a * -1;
    return a;
}

// 재귀 O(2^n)
// 각 케이스에 대해 1) start에 넣거나, 2) link에 넣거나
void go(int idx){
    
    // 1 ~ n번째 선수에 대해 케이스를 구분했을때
    if(idx == n + 1){
        
        // start, link팀 각각의 크기가 n/2로 딱 절반일때
        if(start.size() == n/2 && link.size() == n/2){
            
            // 변수 초기화
            start_sum = 0;
            link_sum = 0;
            
            // 2중 for문으로 돌면서 각 팀의 선수를 고릅니다. O(n^2)
            for(int i=0; i<n/2; i++){
                for(int j=i+1; j<n/2; j++){
                    if(i == j)continue;
                    
                    // 1) 스타트팀 2명 골라서
                    start_first = start[i];
                    start_second = start[j];
                    
                    // 스타트팀 점수 계산
                    start_sum += a[start_first][start_second] + a[start_second][start_first];

                    // 2) 링크팀 2명 골라서
                    link_first = link[i];
                    link_second = link[j];

                    // 링크팀 점수 계산
                    link_sum += a[link_first][link_second] + a[link_second][link_first];
                }
            }
            
            // 절대값을 취해주고, 최소값을 갱신해줍니다.
            result = min(result, abs(start_sum - link_sum));
         
        }
        return;
    }
    
    // idx선수에 대해 두가지 케이스가 존재한다.
    // 1) 스타트 팀에 넣는다.
    start.push_back(idx);
    go(idx + 1);
    start.pop_back();

    // 2) 링크 팀에 넣는다.
    link.push_back(idx);
    go(idx + 1);
    link.pop_back();
}

int main(){
    // 1. 입력
    scanf("%d", &n);
    
    // 2차원 배열에 힘의 정보를 입력받습니다.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    
    // 2. 재귀 수행
    go(1);
    
    // 3. 출력
    printf("%d\n", result);
}

2) 순열

#include <iostream>
#include <vector>
#include <algorithm>
#define max_int 21
/*
 최소값 구할때 제일 큰값으로 초기화하는데
 얼마인지 계산하기 귀찮을때, 단, 변수의 최대 크기가 int범위 안에 들어올때
 2147483647 로 초기화 합니다.
 
 리듬감 있게 외우면 20초 이내에 외워집니다.
 이일~ 사칠사팔~ 삼육사칠~
 */
#define max_val 2147483647
using namespace std;

/*
 시간 복잡도: O(nCn/2 + n^2)
 공간 복잡도: O(n^2)
 사용한 알고리즘: 순열(next_permutation)
 사용한 자료구조: 배열, 리스트
 */

int n, a[max_int][max_int], start_sum, link_sum, start_first, start_second, link_first, link_second, result = max_val;

// 스타트, 링크 팀에 속한 사람들의 번호를 저장할 리스트를 벡터로 생성
vector<int> start, link;

// 최소값 반환
int min(int a, int b){
    return a < b ? a : b;
}

// 절대값 반환
int abs(int a){
    if(a < 0) a = a * -1;
    return a;
}

int main(){
    // 1. 입력
    scanf("%d", &n);
    
    // 2차원 배열에 힘의 정보를 입력받습니다.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    
    // 2. 순열 수행
    // 순열을 저장할 리스트 v를 벡터로 생성합니다.
    vector<int> v;
    for(int i=0; i<n/2; i++) v.push_back(0);
    for(int i=0; i<n/2; i++) v.push_back(1);
    do{
        //스타트팀, 링크팀을 만들고
        vector<int> start, link;
        for(int i=0; i<(int)v.size(); i++){
            // 0일때 스타트팀에 넣어줍니다.
            if(v[i] == 0) start.push_back(i + 1);
            // 1일때 링크팀에 넣어줍니다.
            else link.push_back(i + 1);
        }
        
        start_sum = 0;
        link_sum = 0;
        
        // 2중 for문으로 돌면서 각 팀의 선수를 고릅니다. O(n^2)
        for(int i=0; i<n/2; i++){
            for(int j=i+1; j<n/2; j++){
                if(i == j)continue;
                
                // 1) 스타트팀 2명 골라서
                start_first = start[i];
                start_second = start[j];
                
                // 스타트팀 점수 계산
                start_sum += a[start_first][start_second] + a[start_second][start_first];
                
                // 2) 링크팀 2명 골라서
                link_first = link[i];
                link_second = link[j];
                
                // 링크팀 점수 계산
                link_sum += a[link_first][link_second] + a[link_second][link_first];
            }
        }
        
        // 절대값을 취해주고, 최소값을 갱신해줍니다.
        result = min(result, abs(start_sum - link_sum));
        
    }while(next_permutation(v.begin(), v.end()));
    
    // 3. 출력
    printf("%d\n", result);
}

3) 비트마스크

#include <iostream>
#include <vector>
#include <algorithm>
#define max_int 21
/*
 최소값 구할때 제일 큰값으로 초기화하는데
 얼마인지 계산하기 귀찮을때, 단, 변수의 최대 크기가 int범위 안에 들어올때
 2147483647 로 초기화 합니다.
 
 리듬감 있게 외우면 20초 이내에 외워집니다.
 이일~ 사칠사팔~ 삼육사칠~
 */
#define max_val 2147483647
using namespace std;

/*
 시간 복잡도: O(2^n * n^2)
 공간 복잡도: O(n^2)
 사용한 알고리즘: 비트 마스킹
 사용한 자료구조: 배열, 리스트
 */

int n, a[max_int][max_int], start_sum, link_sum, start_first, start_second, link_first, link_second, result = max_val;

// 스타트, 링크 팀에 속한 사람들의 번호를 저장할 리스트를 벡터로 생성
vector<int> start, link;

// 최소값 반환
int min(int a, int b){
    return a < b ? a : b;
}

// 절대값 반환
int abs(int a){
    if(a < 0) a = a * -1;
    return a;
}

int main(){
    // 1. 입력
    scanf("%d", &n);
    
    // 2차원 배열에 힘의 정보를 입력받습니다.
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &a[i][j]);
        }
    }
    
    for(int i=(1 << (n/2 + 1)) - 1; i < (1 << n); i++){
        vector<int> start, link;
        for(int j=0; j < n; j++){
            if((i & (1 << j)) != 0) start.push_back(j+1);
            else link.push_back(j+1);
            
        }
        
        // start, link팀 각각의 크기가 n/2로 딱 절반일때
        if(start.size() == n/2 && link.size() == n/2){
            // 변수 초기화
            start_sum = 0;
            link_sum = 0;
            
            // 2중 for문으로 돌면서 각 팀의 선수를 고릅니다. O(n^2)
            for(int i=0; i<n/2; i++){
                for(int j=i+1; j<n/2; j++){
                    if(i == j)continue;
                    
                    // 1) 스타트팀 2명 골라서
                    start_first = start[i];
                    start_second = start[j];
                    
                    // 스타트팀 점수 계산
                    start_sum += a[start_first][start_second] + a[start_second][start_first];
                    
                    // 2) 링크팀 2명 골라서
                    link_first = link[i];
                    link_second = link[j];
                    
                    // 링크팀 점수 계산
                    link_sum += a[link_first][link_second] + a[link_second][link_first];
                }
            }
            
            // 절대값을 취해주고, 최소값을 갱신해줍니다.
            result = min(result, abs(start_sum - link_sum));
        }
    }
    
    
    // 3. 출력
    printf("%d\n", result);
}