C. Back and Forth

Editor: 최연웅(yonsweng)

문제 풀이

barn 1에 있는 10개의 bucket 중 하나를 사용해 우유를 옮기고, barn 2에 있는 11개의 bucket(방금 barn 1에서 2로 옮기는 데 사용한 bucket 포함) 중 하나를 다시 barn 1으로 옮기는 작업을 한 세트로 생각합니다.

이 세트를 2번 실행하면 모든 경우의 수를 탐색할 수 있습니다.

시간복잡도: O(N^4) (N: bucket의 개수)

정답 소스 (C++)

#include <iostream>
#include <utility>

using namespace std;

int bucket1[10], bucket2[10];
bool check[1199];  // 802~1198

void back_and_forth(int barn1, int depth) {
    if(depth == 2) {
        check[barn1] = true;
        return;
    }
    for(int i=0; i<10; i++) {
        back_and_forth(barn1, depth + 1);  // Carry bucket1[i] 1->2 and 1<-2.
        for(int j=0; j<10; j++) {
            swap(bucket1[i], bucket2[j]);  // Carry bucket1[i] 1->2 and bucket2[j] 1<-2.
            back_and_forth(barn1 + bucket1[i] - bucket2[j], depth + 1);
            swap(bucket1[i], bucket2[j]);
        }
    }
}

int main() {
    for(int i=0; i<10; i++) cin >> bucket1[i];
    for(int i=0; i<10; i++) cin >> bucket2[i];

    back_and_forth(1000, 0);

    int answer = 0;
    for(int i=802; i<=1198; i++) answer += check[i] ? 1 : 0;
    cout << answer;

    return 0;
}