[도전 14일차] 양팔저울 - KOI 고등부 풀이

※복습 : 

 

※ 백준 2629 양팔저울 문제와 다른 문제입니다.

문제 : 백준 1653 (KOI 2005 고등부 1번)

문제 링크

 

사용 알고리즘 : 완전탐색 (백트래킹)

 

풀이:

도전 6일차 때 풀었던 KOI채점과 같은 맥락으로 K가 10억까지 가능한 것처럼 묘사해 놓았지만,

실제로는 가능한 추의 크기가 9개 이하로 제한되어 있으므로 가능한 모든 추 배치는

3^9 * 5! * 5! 개 미만이다. ( 왼쪽에 넣거나, 넣지 않거나, 오른쪽에 넣는다 + Permutation)

이를 계산하면 2*10^8 정도 인데, 실제로 가능한 배치는 적으므로 완전탐색으로 평형점수지 확인한 다음 정렬해주면 문제를 해결할 수 있다.

 

내 코드는 980ms로 AC 받았다.

허허.. 정말 간당간당해서 오히려 더 성취감이 더 크다.

지난 포스팅 중에 가장 효율적인 코드보다도 빠르게 짤 수 있는 코드를 원한다고 했는데 신이 그 바람을 들으신 걸까? 이렇게 극단적일 줄은 몰랐다.

 

완전탐색 진행에는 여러가지 방법이 있을 수 있는데, 나는 bit을 이용해서 10개의 자리 중에 어떤 자리를 채울지 결정하고, 실제로 채우는 방법으로 진행했다.

 

탐색을 돌릴 때 sum 도 같이 들고 다니면서 왼쪽 자리에 놓을 경우 더해주고, 오른쪽 자리에 놓을 경우 빼주면서, 모든 자리를 채웠을 때 sum==0일 경우 vector 에 추가해주었다.

 

조금이라도 효율을 높이기 위해서 sum<0이 되면 커팅해주었다.

(그 뒤로는 오른쪽 자리만 보므로 sum이 증가할리 없음)

 

코드

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
#define vsort(v) sort(v.begin(),v.end())
using namespace std;
int n,k,cnt,w[10],vis[10],ans[10],chg[513],p[10];
vector<ll> v;
void solve(int bit,int sum){
    if(sum<0) return;
    if(bit==0){
        if(sum==0){
            ll base=1,num=0;
            for(int i=9;i>=0;i--){
                num+=ans[i]*base;
                base*=10;
            }
            v.push_back(num);
        }
        return;
    }
    int first_bit=1<<(31-__builtin_clz(bit)),ord;
    bit^=first_bit; ord=9-chg[first_bit];
    for(int i=0;i<n;i++){
        if(!vis[i]){
            ans[ord]=w[i]; vis[i]=1; 
            solve(bit,sum+w[i]*(ord<5?(5-ord):-(ord-4)));
            ans[ord]=0; vis[i]=0;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)cin>>w[i];
    chg[0]=1;
    for(int i=1;i<10;i++) chg[1<<i]=i;
    cin>>k;
    int s=(1<<5)+1,e=(1<<10)-1;
    v.push_back(0);
    if(k>0){
        for(int bit=s;bit<=e;bit++){
            if(bit&31==0 || __builtin_popcount(bit)>n) continue;
            solve(bit,0);
        }
    }
    vsort(v);
    v.erase(unique(v.begin(),v.end()),v.end());
    if(k>v.size()-1)
        cout<<v.back();
    else
        cout<<v[k];
}

※Sort 안하려고 bit를 썼는데, 결국 bit마다 켜져있는 비트의 수가 다르기 때문에 겹침이 발생하여 Sort를 했다. 다른 분 코드 보니 평범한 완탐( n개의 추에 들어갈 위치 정해주기)로 코드를 짰는데, 620ms 정도 나온다. 

교훈 : 새로운 방법을 시도하고 싶으면, 항상 반례를 모두 체크하자.

 

더 빠른 코드를 짜고 싶은 경우,

맞은 사람에서 bongssi 님 코드에 설명이 아주 잘 나와있다.