USACO 1.4 - Mother's Milk

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.

PROGRAM NAME: milk3

INPUT FORMAT

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

SAMPLE INPUT (file milk3.in)

8 9 10

OUTPUT FORMAT

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.

SAMPLE OUTPUT (file milk3.out)

1 2 8 9 10

SAMPLE INPUT (file milk3.in)

2 5 10

SAMPLE OUTPUT (file milk3.out)

5 6 7 8 9 10

출처: http://train.usaco.org/

A, B, C 세 개의 우유통이 있다. A, B, C의 용량은 1~20 자연수이고 A, B는 비어있고 C는 가득 차있다.

한 통에서 다른 통으로 옮겨 담는데 통이 꽉 차거나 붓는 통이 빌 때 까지만 옮겨 담을 수 있고. 우유는 버릴 수 없다.

이 상황에서 A통이 비어 있을때 C통에 담겨 있을 수 있는 모든 경우의 수를 출력하는 프로그램을 작성하시오.

memoization 으로 시간복잡도를 낮추는 방법으로 풀어봤습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
 
int capacity[3];
int cache[21][21][21];
 
void pourMilk(int milks[3], int from, int to)
{
    int pauredMilk = milks[from];
    if (pauredMilk > (capacity[to] - milks[to]))
        pauredMilk = capacity[to] - milks[to];
    milks[from] -= pauredMilk;
    milks[to] += pauredMilk;
}
 
void solve(int milks[3])
{
    if (cache[milks[0]][milks[1]][milks[2]] == 0)
    {
        cache[milks[0]][milks[1]][milks[2]] = 1;
 
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                if (j == i)
                    continue;
                int temp[3] = { milks[0], milks[1], milks[2] };
                pourMilk(temp, i, j);
                solve(temp);
            }
        }
    }
}
int main()
{
    ifstream fin("milk3.in");
    ofstream fout("milk3.out");
 
    fin >> capacity[0] >> capacity[1] >> capacity[2];
 
    int temp[3] = { 0, 0, capacity[2] };
    solve(temp);
 
    bool isFirst = true;
    for (int c = 0; c <= capacity[2]; c++)
    {
        for (int b = 0; b <= capacity[1]; b++)
        {
            if (cache[0][b][c] == 1)
            {
                if (isFirst == false)
                    fout << " ";
                fout << c;
                isFirst = false;
                break;
            }
        }
    }
    fout << endl;
    
    fin.close();
    fout.close();
    return 0;
}