[백준(BOJ) 16771번] Back and Forth 풀이

문제 : https://www.acmicpc.net/problem/16771

 

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

 

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

 

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

#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;
}