728x90
dfs(백트래킹)을 이용해서 만들 수 있는 모든 조합의 경우를 다 따지는 문제이다.
처음엔 조합을 이용한 브루트포스이겠거니 생각했지만 조합을 어떻게 구현하는지 생각이 안났다..
해서 dfs을 가지고 순열 및 조합을 구현하는 코드를 공부 한 후에 다시 문제를 풀었다.
stl라이브러리 중 next_permutation으로 구할 수 있었지만, 시간복잡도가 너무 크기 때문에
직접 재귀로 구현하는 것이 낫다고 한다. 아래사이트를 참고해서 공부했다.
https://paris-in-the-rain.tistory.com/35
순열, 조합 알고리즘 - DFS로 구하기(백트래킹), C++, Python
순열, 조합은 정말정말 많이 나오는데 cpp의 stl 라이브러리 중 next_permutation으로 구할 수 있다. 하지만 next_permutation은 N이 20만 넘어가도 터질 위험에 처한다.. 시간복잡도가 크기 때문이다. N이 10
paris-in-the-rain.tistory.com
조합은 순서를 고려하지 않기 때문에 (1,2,3,4,5)중에 3개를 고른다고 했을 때
(1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5) 총 10가지 경우의 수(5C3)가 나온다.
이 문제의 경우도 단순히 '능력치의 차이'만을 구하는 것이기 때문에 순서를 고려하지 않는
조합으로 풀 수가 있다. 조합이 하나 완성될 때마다 차이를 갱신해주도록 만들었다.
Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
const int MAX = 21;
int arr[MAX][MAX];
int now[MAX];
bool visited[MAX] = { 0, };
int n;
int maxDiff = 2000;
void check()
{
vector<int> v1;
vector<int> v2;
int startpoint = 0;
int linkpoint = 0;
for (int i = 1; i <= n; i++)
{
if (visited[i] == true)
v1.push_back(now[i]);
else
v2.push_back(now[i]);
}
//start, link 점수구하기
for (int i = 0; i < v1.size(); i++)
{
for (int j = 0; j < v1.size(); j++)
{
if (i == j)
continue;
startpoint += arr[v1[i]][v1[j]];
linkpoint += arr[v2[i]][v2[j]];
}
}
maxDiff = min(maxDiff, abs(startpoint - linkpoint));
} void dfs_combi(int idx, int cnt)
{
if (cnt == n / 2)
{
check();
return;
}
for (int i = idx; i <= n; i++)
{
if (visited[i] == true)
continue;
visited[i] = true;
dfs_combi(i, cnt + 1);
visited[i] = false;
}
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> arr[i][j];
}
}
//n에따라 1~n까지 수열 now를 만든다.
for (int i = 1; i <= n; i++)
now[i] = i;
dfs_combi(1, 0);
cout << maxDiff;
return 0;
}
|
cs |
|
|
|
728x90
'Algorithm > 삼성 SW기출문제' 카테고리의 다른 글
| [백준] 13460 구슬 탈출 2 (0) | 2022.02.22 |
|---|
댓글