※문제 해결 과정
A, B, C물통이 있고 초기에 C만 꽉차있다. 여기서 물통의 물이 옮겨지는 경우의 수를 BFS로 물통들의
잔량을 큐에 저장하면서 돌려주면 된다.
먼저 C->A물통으로 옮기는경우와 C->B물통으로 옮기는 경우가 있다.
또 B->C물통으로 옮기는 경우와 B-> A물통으로 옮기는 경우
A->C물통으로 옮기는 경우, A->B물통으로 옮기는 경우를 따져주면 된다. 중요한건 A물통의 잔량이
비었다면 그때의 C물통에 있을 수있는 물의 양이므로 물을 옮기는 과정에서 A물통의 잔량이 없다면
물의 양이 1~200까지 밖에 주어지지 않으므로 그때의 Array_[C의 잔량] = true; 이런식으로 체크해주
면된다. 여기서 방문처리와 같은 배열처럼 같은 물의 양 조합이 또나오면 번복하는 연산이 일어날수 있
으므로 A,B물통의 잔량을 이차원배열로 체크를 해준다. Array_[A잔량][B잔량] = true;
(물통이 2개라서 이런식으로 체크가 가능한것이다..ㅠ)
다돌려주고 나서 1~200까지 쭉 올라가면서 체크된 c의 잔량 배열을 출력해주면
AC를 받을수 있을 것이다.
<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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | //pda_pro12 #include<algorithm> #include<iostream> #include<queue> using namespace std; bool chk[201][201]; // a, b 물통의 물의 양을 확인해주는 배열 bool ans[201]; // c물통의 물의 양을 확인해주는 배열 int a, b, c, sum; queue<pair<int, int>> q; int main() { cin >> a >> b >> c; chk[0][0] = true; ans[c] = true; sum = c; // c물통에만 가득차있으므로 손실되는 물이 없으면 총량은 c의 들이와 같음 q.push(make_pair(0, 0)); while (!q.empty()) { int x = q.front().first; int y = q.front().second; int z = sum - (x + y); // q.pop(); int nx, ny, nz; nx = x; ny = y; nz = z; ny += nx; nx = 0; if (ny >= b) { // 물의 이동시 살펴줘야할 조건 nx = ny - b; ny = b; } if (!chk[nx][ny]) { chk[nx][ny] = true; q.push(make_pair(nx, ny)); if (nx == 0) { ans[nz] = true; } } nx = x; ny = y; nz = z; nz += nx; nx = 0; if (nz >= c) { nx = nz - c; nz = c; } if (!chk[nx][ny]) { chk[nx][ny] = true; q.push(make_pair(nx, ny)); if (nx == 0) { ans[nz] = true; } } nx = x; ny = y; nz = z; nz += ny; ny = 0; if (nz >= c) { ny = nz - c; nz = c; } if (!chk[nx][ny]) { chk[nx][ny] = true; q.push(make_pair(nx, ny)); if (nx == 0) { ans[nz] = true; } } nx = x; ny = y; nz = z; nx += ny; ny = 0; if (nx >= a) { ny = nx - a; nx = a; } if (!chk[nx][ny]) { chk[nx][ny] = true; q.push(make_pair(nx, ny)); if (nx == 0) { ans[nz] = true; } } nx = x; ny = y; nz = z; ny += nz; nz = 0; if (ny >= b) { nz = ny - b; ny = b; } if (!chk[nx][ny]) { chk[nx][ny] = true; q.push(make_pair(nx, ny)); if (nx == 0) { ans[nz] = true; } } nx = x; ny = y; nz = z; nx += nz; nz = 0; if (nx >= a) { nz = nx - a; nx = a; } if (!chk[nx][ny]) { chk[nx][ny] = true; q.push(make_pair(nx, ny)); if (nx == 0) { ans[nz] = true; } } } for (int i = 0; i <= c; i++) { if (ans[i]) { cout << i << ' '; } } return 0; } |