백준 14889 스타트와 링크

skyepodium·2019년 7월 23일
백준14889백트래킹비트마스킹순열스타트와링크
2

sw 역량 테스트

목록 보기
3/12
post-thumbnail

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

문제

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

  1. n 총 인원수 (4 ≤ n ≤ 20, n은 짝수)

  2. 한 팀의 힘은 다음과 같이 계산
    한 팀에 1, 3, 5가 속했을때 2명씩 추출한다.
    팀 총합 = s[1][3] + s[3][1] + s[1][5] + s[5][1] + s[3][5] + s[5][3]

  3. 두팀의 총 힘 차이의 최소값을 구하세요

  4. 예시

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

풀이 과정

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가지 입니다.

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

까짓거 다해봅시다.

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);
}
profile
skyepodium
callmeskye
이전 포스트

백준 14501 퇴사

다음 포스트

백준 16235 나무 재테크

0개의 댓글