-
[백준 14889번 - 스타트와 링크] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 9. 19. 20:12728x90반응형
백준 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'알고리즘 > 삼성SW역량테스트기출' 카테고리의 다른 글
[백준 15684번 - 사다리 타기] C++ 풀이 (0) 2021.09.23 [백준 14891번 - 톱니바퀴] C++ 풀이 (0) 2021.09.23 [백준 14503번 - 로봇 청소기] C++ 풀이 (0) 2021.09.19 [백준 14500번 - 테르로미노] C++ 풀이 (0) 2021.09.19 [백준 14499번 - 주사위 굴리기] C++ 풀이 (0) 2021.09.19