반응형
https://www.acmicpc.net/problem/12886
12886번: 돌 그룹
오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려
www.acmicpc.net
[ 문제풀이 ]
1. 돌의 전체 합을 sum 변수에 저장합니다.
2. 상태를 저장할 visited [1501][1501] 배열을 만듭니다. A와 B만 저장하는 이유는 C = sum - A - B로 정의할 수 있기 때문입니다.
3. queue에 현재 상태를 넣고 for문을 돌리면서 stone [ i ] > stone [ j ] 일 경우 방문한 경우가 아닐 때 A = stone [ i ]-stone [ j ], B = stone [ j ] * 2로 저장하여 다시 queue에 넣어줍니다.
4. 위과정을 반복하다가 A == B && B == C일 경우 1을 출력해주고, 아닐 경우 0을 출력해줍니다.
[ 소스코드 ]
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 | #include<iostream> #include<queue> using namespace std; int A, B, C; int sum; int visited[1501][1501]; int main() { scanf("%d %d %d", &A, &B, &C); sum = A + B + C; if (sum% 3 != 0) { printf("%d", 0); return 0; } queue<pair<int, int>> q; q.push({ A,B }); visited[A][B] = 1; visited[B][A] = 1; while (!q.empty()) { int A = q.front().first; int B = q.front().second; int C = sum - A - B; q.pop(); if (A == B && B == C) { printf("%d", 1); return 0; } int stone[3] = { A,B,C }; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (stone[i] > stone[j]) { int AA = stone[i] - stone[j]; int BB = stone[j] * 2; if (visited[AA][BB] != 1 && visited[BB][AA] != 1) { visited[AA][BB] = 1; visited[BB][AA] = 1; q.push({ AA,BB }); } } } } } printf("%d", 0); } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 13913번 - 숨바꼭질 4 (C++) (0) | 2022.11.12 |
|---|---|
| [ 백준 ] 1976번 - 여행 가자 (C++) (0) | 2022.11.11 |
| [ 백준 ] 2281번 - 데스노트 (C++) (0) | 2022.11.09 |
| [ 백준 ] 7569번 - 토마토 (C++) (0) | 2022.11.08 |
| [ 백준 ] 2195번 - 문자열 복사 (C++) (0) | 2022.11.07 |