[2251번] 물통

문제 출처 :

https://www.acmicpc.net/problem/2251

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

2. 수학적 지식

이 문제는 x->y로 물을 옮길 때 어떻게 되는지만 하나의 케이스를 알아내면 모든 케이스에 대해 접목할 수 있다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

// b->a     // b에 물이 있고, a가 가득 안찼을 때     if (nowB != 0 && nowA < maxA)     {         int leftA = maxA - nowA;           // b의 물 양이 a의 남은 공간보다 크면         if (nowB > leftA)         {             nowB -= leftA;             nowA = maxA;         }           // b의 물 양이 a의 남은 공간보다 작거나 같으면         else         {             nowA += nowB;             nowB = 0;         }         q.push({ nowA, nowB, nowC });     }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

처음에는 위와같이 알고리즘을 생각하였다.

b에 물이 있고, a가 아직 안차있다면

leftA를 통해 남은 a의 공간을 구해주고

b의 물 양이 a의 공간보다 많으면 b는 물을 덜 비우게 되니 nowB -= leftA가 되고

a는 물을 가득 채우는 꼴이 되니 nowA= maxA가 된다.

그 외의 경우에는(b의 물이 a공간에 충분히 다 들어갈 수 있다면)

nowA에 모든 B의 물이 들어올것이고

b의 물통에는 물이 없어질 것이다.

그렇게 q에 현재 물의 정보를 보내면 된다고 생각하고 

q.push({nowA, nowB, nowC})로 큐에 삽입하였다.

이 방식을 이용하여 압축시킨 내용을 아래 코드에 작성해 두었다.

소스 코드 : 

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 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167

#include <cstdio> #include <iostream> #include <queue>   using namespace std;   typedef struct _INFO_ {     int a, b, c; }INFO;   queue<INFO> q; bool ans[201]; bool visit[201][201][201]; int maxA, maxB, maxC;   /*     이용한 알고리즘     // b->a     // b에 물이 있고, a가 가득 안찼을 때     if (nowB != 0 && nowA < maxA)     {         int leftA = maxA - nowA;         // b의 물 양이 a의 남은 공간보다 크면         if (nowB > leftA)         {             nowB -= leftA;             nowA = maxA;         }         // b의 물 양이 a의 남은 공간보다 작거나 같으면         else         {             nowA += nowB;             nowB = 0;         }         q.push({ nowA, nowB, nowC });     } */   int main() {       scanf("%d %d %d", &maxA, &maxB, &maxC);       q.push({ 0,0,maxC });          while (!q.empty())     {         int nowA, nowB, nowC;           nowA = q.front().a;         nowB = q.front().b;         nowC = q.front().c;           //cout << "A :: " << nowA << " B :: " << nowB << " C :: " << nowC << endl;         q.pop();           if (visit[nowA][nowB][nowC])             continue;           visit[nowA][nowB][nowC] = true;         if(nowA == 0)             ans[nowC] = true;           // c->a         // c에 물이 있고, a가 가득 안찼을 때         if (nowC != 0 && nowA < maxA)         {             int leftA = maxA - nowA;               // c의 물 양이 a의 남은 공간보다 크면             if (nowC > leftA)                 q.push({ maxA, nowB, nowC-leftA });               // c의 물 양이 a의 남은 공간보다 작거나 같으면             else                 q.push({ nowA + nowC, nowB, 0 });         }           // c->b         // c에 물이 있고, b가 가득 안찼을 때         if (nowC != 0 && nowB < maxB)         {             int leftB = maxB - nowB;               // c의 물 양이 b의 남은 공간보다 크면             if (nowC > leftB)                 q.push({ nowA, maxB, nowC -leftB });               // c의 물 양이 b의 남은 공간보다 작거나 같으면             else                 q.push({ nowA, nowB + nowC, 0 });         }           // b->a         // b에 물이 있고, a가 가득 안찼을 때         if (nowB != 0 && nowA < maxA)         {             int leftA = maxA - nowA;               // b의 물 양이 a의 남은 공간보다 크면             if (nowB > leftA)                 q.push({ maxA, nowB - leftA, nowC });               // b의 물 양이 a의 남은 공간보다 작거나 같으면             else                 q.push({ nowA + nowB, 0, nowC });         }             // b->c         // b에 물이 있고, c가 가득 안찼을 때         if (nowB != 0 && nowC < maxC)         {             int leftC = maxC - nowC;               // b의 물 양이 c의 남은 공간보다 크면             if (nowB > leftC)                 q.push({ nowA, nowB - leftC, maxC });               // b의 물 양이 c의 남은 공간보다 작거나 같으면             else                 q.push({ nowA, 0, nowC + nowB});         }           // a->c         // a에 물이 있고, c가 가득 안찼을 때         if (nowA != 0 && nowC < maxC)         {             int leftC = maxC - nowC;               // a의 물 양이 c의 남은 공간보다 크면             if (nowA > leftC)                 q.push({ nowA - leftC, nowB, maxC });               // a의 물 양이 c의 남은 공간보다 작거나 같으면             else                 q.push({ 0, nowB, nowC + nowA });         }           // a->b         // a에 물이 있고, b가 가득 안찼을 때         if (nowA != 0 && nowB < maxB)         {             int leftB = maxB - nowB;               // a의 물 양이 b의 남은 공간보다 크면             if (nowA > leftB)                 q.push({ nowA - leftB, maxB, nowC });               // a의 물 양이 b의 남은 공간보다 작거나 같으면             else                 q.push({ 0, nowB + nowA, nowC });         }     }       for (int i = 0; i <= maxC; i++)     {         if (ans[i] == true)             printf("%d ", i);     }       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus