[백준] 16987 계란으로 바위치기

 

완전탐색 문제다

처음에 최대 8!인 순열이라고 생각해서 예제가 안나왔다

근데 계란을 칠 때는 순서는 필요 없다

따라서 최대 8^7의 시간을 갖게 되는것 같다 대충 2^21?

 

우선 어떤 계란을 칠지 배열에 넣어주고

그대로 한번 계산해보면 답은 잘 나온다!

 

계란 순서를 정하고 solve함수를 돌려서 시간이 좀 느린데

가지치기를 통해 한번에하면 좀 빠르다!

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int n,ans;
int order[11];
pair<int,int> arr[11];
pair<int,int> temp[11];
 
int solve(){
    int ret=0;
    for(int i=0;i<n;i++){
        int now =i,next =order[i];
        if(now==next) return 0;
        if(temp[now].first <=0 || temp[next].first<=0) continue;
        temp[now].first-=temp[next].second;
        temp[next].first-=temp[now].second;
    }
    for(int i=0;i<n;i++) if(temp[i].first<=0) ret+=1;
    return ret;
}
 
void pick(int cnt){
    if(cnt==n) {
        for(int i=0;i<n;i++) temp[i]=arr[i];
        ans = max(ans,solve()); return;
    }
    for(int i=0;i<n;i++){
        order[cnt]=i;
        pick(cnt+1);
    }
}
 
int main(){
    scanf(" %d",&n);
    for(int i=0;i<n;i++) order[i]=i;
    for(int i=0;i<n;i++) scanf(" %d %d",&arr[i].first,&arr[i].second);
    pick(0);
    printf("%d\n",ans);
}