SWEA 3234번: 준환이의 양팔저울

문제

문제 바로가기> SWEA 3234번: 준환이의 양팔저울

SW Expert Academy

 

풀이

" 오른쪽 추의 무게 <= 왼쪽 추의 무게 " 이므로, backtracking 시 이 부분을 고려하여 가지치기를 진행할 수 있다. 하지만,, 그래도 시간 초과가 발생하기 때문에,, 한 가지 가지치기를 더 해주어야 한다. 바로 남은 추들을 어떻게 올려도 상관없는 경우이다! 이때는 문제에서 제시해 준 공식을 정답에 더해주고 return 해주면 된다! 그렇게 하면 추가로 일일이 탐색할 필요가 없겠죠?! 😎

 

#include<iostream>
#include<cstring>
#define MAX 10
using namespace std;

int N;
int ans;
int total;
int weight[MAX];
bool isuse[MAX];
int exponential[MAX] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
int factorial[MAX] = {0, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

void init(){
    ans = 0;
    total = 0;
    memset(isuse, false, sizeof(isuse));
}

void input(){
    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> weight[i];
        total+=weight[i];
    }
}

void dfs(int cnt, int left, int right){

    if(cnt == N){ // 모든 무게추를 올린 경우
        ans++;
        return;
    }

    if(total-left <= left){ // 남은 추를 어떻게 올려도 상관 없는 경우 
        ans += exponential[N-cnt] * factorial[N-cnt]; // 남은 추를 올리는 경우의 수 (시간 초과 방지!)
        return ;
    }

    for(int i=0; i<N; i++){
        if(isuse[i]) continue;
        isuse[i] = true;
        dfs(cnt+1, left+weight[i], right);
        if(right+weight[i] <= left) dfs(cnt+1, left, right+weight[i]); // 오른쪽 <= 왼쪽
        isuse[i] = false;
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    for(int t=1; t<=T; t++){
        init();
        input();
        dfs(0, 0, 0);
        cout << "#" << t << " " << ans << "\n"; 
    }
}