https://www.acmicpc.net/problem/12886
12886번: 돌 그룹
오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려
www.acmicpc.net
하나의 시작점이 있을 때
다른 정점으로 갈 수 있는지 없는지 보는 문제
check 배열이 필요.
정점 (A, B, C)
시간복잡도 1500 ^ 3 -> 33억..
돌의 전체 개수는 같으므로
2개만 처리를 하면 나머지 하나는 자동으로 정해지게 된다.
정점의 정의를 (A, B)
(X, Y) -> (X + X, Y - X) 합이 같다!!
입력 N = A + B + C --> C = N - A - B
그럼 시간복잡도가 1500 ^ 2로 바뀜
a, b, c,의 합이 3으로 나누어 떨어지지 않으면
그냥 불가능이니까 그 조건 넣자.
돌의 개수가 각각 1000개는 못 넘을 거 같다.
그래도 여유롭게 1500으로 잡자.
|
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
|
#include <iostream>
#include <vector>
using namespace std;
bool check[1501][1501];
int sum;
void dfs(int a, int b)
{
if (check[a][b]) return;
check[a][b] = true;
int dol[3] = { a, b, sum - a - b };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (dol[i] < dol[j])
{
int change[3] = { a, b, sum - a - b };
change[i] += dol[i];
change[j] -= dol[i];
dfs(change[0], change[1]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c;
cin >> a >> b >> c;
sum = a + b + c;
if (sum % 3 != 0)
{
cout << 0 << '\n';
return 0;
}
dfs(a, b);
if (check[sum / 3][sum / 3])
{
cout << 1 << '\n';
}
else
{
cout << 0 << '\n';
}
return 0;
}
|
cs |
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (dol[i] < dol[j])
이러면 굳이 조합을 쓰지 않아도 됨.
別解
BFS로도 풀 수 있다.
|
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
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
queue <pair<int, int>> q;
bool check[1501][1501];
// sum은 전역변수
int sum;
void bfs(int a, int b)
{
check[a][b] = true;
q.push(make_pair(a, b));
while (!q.empty())
{
int tmp_a = q.front().first;
int tmp_b = q.front().second;
q.pop();
int dol[3] = { tmp_a, tmp_b, sum - tmp_a - tmp_b };
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (dol[i] < dol[j])
{
int change[3] = { tmp_a, tmp_b, sum - tmp_a - tmp_b };
change[i] += dol[i];
change[j] -= dol[i];
if (!check[change[0]][change[1]])
{
check[change[0]][change[1]] = true;
q.push(make_pair(change[0], change[1]));
}
}
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int a, b, c;
cin >> a >> b >> c;
sum = a + b + c;
if (sum % 3 != 0)
{
cout << 0 << '\n';
return 0;
}
bfs(a, b);
if (check[sum / 3][sum / 3])
{
cout << 1 << '\n';
}
else
{
cout << 0 << '\n';
}
return 0;
}
|
cs |
