2020. 4. 14. 23:42ㆍPS/도전
※복습 :
※ 백준 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이 증가할리 없음)
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
//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];
}
|
cs |
※Sort 안하려고 bit를 썼는데, 결국 bit마다 켜져있는 비트의 수가 다르기 때문에 겹침이 발생하여 Sort를 했다. 다른 분 코드 보니 평범한 완탐( n개의 추에 들어갈 위치 정해주기)로 코드를 짰는데, 620ms 정도 나온다.
교훈 : 새로운 방법을 시도하고 싶으면, 항상 반례를 모두 체크하자.
더 빠른 코드를 짜고 싶은 경우,
맞은 사람에서 bongssi 님 코드에 설명이 아주 잘 나와있다.
'PS > 도전' 카테고리의 다른 글
[도전 16일차] 트리의 높이와 너비 - KOI 고등부 풀이 (0) | 2020.04.16 |
---|---|
[도전 15일차] 경비행기, 두 배열의 합 - KOI 고등부 풀이 (0) | 2020.04.15 |
[도전 13일차] 잠수함 식별 - KOI 고등부 풀이 (2) | 2020.04.13 |
[도전 12일차] 돌다리 건너기 - KOI 고등부 풀이 (0) | 2020.04.13 |
(※도전 완료) [도전 11일차] 백준 6990 달팽이 (0) | 2020.04.09 |