| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 2056 | 910 | 660 | 46.742% |
문제
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이 때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, C가 주어진다.
출력
첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.
예제 입력
8 9 10
예제 출력
1 2 8 9 10
힌트
>> 소감
어떻게 풀어야 할 지는 감이 금방 왔지만 구현이 오래걸렸다.
아직도 준비가 많이 필요한 것으로 보여진다.
나는 dfs 를 이용하여 구현했는데, 다른 풀이에서는 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 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 | #include <iostream> #include <stack> #include <vector> #include <algorithm> using namespace std; int visited[200][200][200] = { 0 }; int capacity[3]; int now_water[3] = { 0 }; vector<int> answer_vec; int move_map[6][2] = { {0,1},{0,2},{1,0},{1,2},{2,0},{2,1} }; // 방문한 노드 1로 표시 void plusVisited() { visited[now_water[0]][now_water[1]][now_water[2]] = 1; } // 방문 여부 리턴 int isVisited() { if (visited[now_water[0]][now_water[1]][now_water[2]]) return 1; else return 0; } // 정답이면 vec에 넣는다. void answerPush() { if (now_water[0] == 0 ) answer_vec.push_back(now_water[2]); } int dfs(int depth, int from, int to) { //cout << depth << " from = " << from << " to = " << to << " _ " << now_water[0] << "/" << now_water[1] << "/" << now_water[2] << endl; // 현재 정보들 받아오기 위한 행렬 int sub_now_waters[3]; // stack 에 있는 내용 받아오기 pair<int, int> now_move = pair<int, int>(from, to); // from 물통에서의 용량이 0 이면 그냥 종료 if (now_water[now_move.first] == 0) return -1; // to 물통이 다 차있으면 그냥 종료 if (now_water[now_move.second] == capacity[now_move.second]) return -1; // 만약 from 물통에서의 남은 물의 용량이 to 물통에서 넣을 수 있는 물의 용량보다 크다면 if (now_water[now_move.first] > capacity[now_move.second] - now_water[now_move.second]) { now_water[now_move.first] -= capacity[now_move.second] - now_water[now_move.second]; now_water[now_move.second] = capacity[now_move.second]; } // 반대로 넣을 수 있는 물의 용량이 작다면 else { now_water[now_move.second] += now_water[now_move.first]; now_water[now_move.first] = 0; } // 방문한 노드면 그냥 종료 if (isVisited()) { return 1; } // 현재 상태 방문 저장 plusVisited(); // 만약 A의 용량이 0이면 해당 C의 용량을 답에 저장 answerPush(); // 현재 노드 상태 저장 for (int i = 0; i < 3; i++) { sub_now_waters[i] = now_water[i]; } // 다음 이동 경로 push for (int i = 0; i < 6; i++) { dfs(depth + 1, move_map[i][0], move_map[i][1]); // 원래 상태로 복귀 for (int i = 0; i < 3; i++) { now_water[i] = sub_now_waters[i]; } } return 0; } int main() { for (int i = 0; i < 3; i++) { cin >> capacity[i]; } // 초기 물 채워주기 now_water[2] = capacity[2]; // 방문한 노드에 추가 plusVisited(); // 정답에 추가 answerPush(); // 다음 이동 경로 push for (int i = 4; i < 6; i++) { dfs(0, move_map[i][0], move_map[i][1]); // 원래 상태로 복귀 now_water[0] = now_water[1] = 0; now_water[2] = capacity[2]; } sort(answer_vec.begin(), answer_vec.end()); for (int i = 0; i < answer_vec.size(); i++) cout << answer_vec[i] << " "; return 0; } | cs |
>> queue 를 이용한 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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | #include<cstdio> #include<queue> #pragma warning(disable :4996) using namespace std; struct Data { int a, b, c; }; //대문자 A,B,C 는 각 물통에 담을 수 있는 물의 최대용량 //소문자 a,b,c 는 현재 물통에 담아져 있는 물의 용량 //chk[a의 물의 양][b의 물의 양] int A, B, C; bool chk[202][202],ans[202]; void bfs() { queue <Data> q; q.push({0,0,C}); while (!q.empty()) { Data now = q.front(); q.pop(); if (chk[now.a][now.b]) continue; chk[now.a][now.b] = true; if (now.a == 0) ans[now.c] = true; //a->b if (now.a + now.b > B) q.push({ (now.a + now.b) - B,B,now.c }); else q.push({0,now.a+now.b,now.c}); //a->c if (now.a + now.c > C) q.push({ (now.a + now.b) - C,now.b,C }); else q.push({0,now.b,now.a+now.c}); //b->a if (now.b + now.a > A) q.push({ A,(now.b + now.a) - A,now.c }); else q.push({now.b+now.a, 0, now.c}); //b->c if (now.b + now.c > C) q.push({ now.a,(now.b + now.c) - C,C }); else q.push({now.a, 0, now.b+now.c}); //c->a if (now.c + now.a > A) q.push({ A,now.b,(now.c + now.a) - A }); else q.push({now.c+now.a,now.b,0}); //c->b if (now.c + now.b > B) q.push({ now.a,B,(now.c + now.b) - B }); else q.push({now.a,now.c+now.b,0}); } } void print() { for (int i = 0; i <= C; i++) { if (ans[i]) printf("%d ", i); } } int main(void) { scanf("%d %d %d", &A, &B, &C); bfs(); print(); return 0; } | cs |