ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [백준 14889번 - 스타트와 링크] C++ 풀이
    알고리즘/삼성SW역량테스트기출 2021. 9. 19. 20:12
    728x90
    반응형

    백준 14889번.

    총 n 명을 n/2 명씩 두 팀으로 나누고, 각 팀의 능력치 합을 구해서 차이를 최소로 하도록 하는 문제이다.

    만약 각 팀에 3명씩 있고, 1,2,3번이 스타트팀, 3,4,5번이 링크팀이라면,

    스타트팀 : S12 + S21 + S13 + S31 + S23 + S32

    링크팀 : S34 + S43 + S35 + S53 + S45 + S54 가 된다.

    사용한 알고리즘

    - 백트래킹

     

    순차적으로 탐색하면서 해당 맴버를 선택하거나/선택하지 않거나. 해서 함수를 호출하도록 했다.

    depth 가 n / 2 이 되면 호출을 멈추도록 재귀를 구현하였다. 그리고 거기서 두 팀 멤버 능력치의 차를 구해서 기존거보다 더 작으면 갱신해주었다.

     

    완성된 코드

    #include <stdio.h>
    #include <vector>
    #include <stack>
    #include <math.h>
    
    using namespace std;
    
    int n;
    vector<vector<int>> v;
    
    int ans = 1001;
    
    void dfs(int x, vector<int> s, vector<bool> visited) {
    	if (s.size() == n / 2) {
    		int a1 = 0;
    		int a2 = 0;
    		for(int i = 0; i < s.size(); ++i) {
    			for(int j = 0; j < s.size(); ++j) {
    				if (s[i] != s[j]) {
    					a1 += v[s[i]][s[j]];
    				}
    			}
    		}
    		vector<int> v2;
    		for(int i = 0; i < n; ++i) {
    			if (visited[i] == false) {
    				v2.push_back(i);
    			}
    		}
    		for(int i = 0; i < v2.size(); ++i) {
    			for(int j = 0; j < v2.size(); ++j) {
    				if (i != j) {
    					a2 += v[v2[i]][v2[j]];
    				}
    			}
    		}
    		ans = (ans > abs(a1 - a2)) ? abs(a1 - a2) : ans;
    		return;
    	} else {
    		for(int i = x; i < n; ++i) {
    			s.push_back(i);
    			visited[i] = true;
    			dfs(i + 1, s, visited);
    			visited[i] = false;
    			s.pop_back();
    		}
    	}
    }
    
    int main() {
    	scanf("%d", &n);
    	vector<bool> visited;
    	v.assign(n + 1, vector<int>(n + 1));
    	visited.assign(n + 1, false);
    	for(int i = 0; i < n; ++i) {
    		for(int j = 0; j < n; ++j) {
    			scanf("%d", &v[i][j]);
    		}
    	}
    	vector<int> s;
    	dfs(0, s, visited);
    	printf("%d\n", ans);
    }
    728x90

    댓글

Designed by Tistory.