Problem 1.5.3 Mother's Milk

출처: https://train.usaco.org/usacogate

---

문제 설명

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out. 

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

입력 

A single line with the three integers A, B, and C.

출력

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when 
bucket A is empty.

입력 예

8 9 10

출력 예

1 2 8 9 10

---

문제 풀이

water jug problem 이라고 불리는 물통 사이에서 물을 옮기는 문제이다. 여기서는 물통 3개를 이용하므로, 3 water jug problem이라고 할 수 있다. 시작할때 가지고 있는 물의 양(0, 0, C)에서 물통 사이에서 한번에 옮길 수 있는 6가지 경우들을 재귀적으로 검색한다. 한번 검색한 곳은 다시 검색하지 않도록 확인해서, 검색을 종료하도록 한다. 문제 조건에 따라서 물통 A가 비어 있을때 물통 C의 양을 기록해서 출력한다.

프로그램 내용

#define BUCKET_LIMIT 21

vector <int> record(BUCKET_LIMIT, 0); /// possible amount record
vector <vector <int>> visited(BUCKET_LIMIT, vector<int>(BUCKET_LIMIT,0)); /// mark visit
vector <int> capa(3); /// store bucket status

void pour(int &from, int &to, int cpfrom, int cpto);
void search(int a, int b, int c); /// check all possible case

int main() {
    int A, B, C;
    fin >> A >> B >> C;

/// initial
    /// Bucket A : 0, Bucekt B: 0, Bucket C: full
    capa[0] = A;    capa[1] = B;    capa[2] = C;

    search(0, 0, C);

 

Chapter 1. Getting started ( link )