[BOJ][백준]브루트 포스-17610번 양팔저울

https://www.acmicpc.net/problem/17610

17610번: 양팔저울

문제

무게가 서로 다른 k개의 추와 빈 그릇이 있다. 모든 추의 무게는 정수이고, 그릇의 무게는 0으로 간주한다. 양팔저울을 한 번만 이용하여 원하는 무게의 물을 그릇에 담고자 한다. 주어진 모든 추 무게의 합을 S라 하자. 예를 들어, 추가 3개이고 그 무게가 각각 {1, 2, 6}이면, S = 9이고, 양팔 저울을 한번만 이용하여 1부터 S사이 모든 정수에 대응하는 물을 다음과 같이 그릇에 담을 수 있다. 여기서, X는 그릇에 담는 물의 무게를 나타내고, □는 그릇을 나타낸다.

X123456789

□:1

□:2

□:(1+2)

(□+2):6

(□+1):6

□:6

□:(1+6)

□:(2+6)

□:(1+2+6)

만약 추의 무게가 {1, 5, 7}이면 S = 13이 되고, 양팔저울을 한 번만 사용하여 그릇에 담을 수 있는 무게는 {1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13}이다. 즉, 1부터 S사이 수 가운데 9와 10에 대응하는 무게의 물을 그릇에 담는 것은 불가능하다.

k(3 ≤ k ≤ 13)개 추 무게 g1, g2, ..., gk가 주어질 때, 1부터 S사이에 있는 정수 중, 양팔 저울을 한번만 이용하여서는 측정이 불가능한 경우의 수를 찾는 프로그램을 작성하고자 한다.

입력

입력의 첫 줄에는 추의 개수를 나타내는 정수 k(3 ≤ k ≤ 13)가 주어진다. 다음 줄에는 k개의 정수 gi(1 ≤ gi ≤ 200,000)가 공백으로 구분되어 주어지는데 이는 각 추의 무게를 나타낸다.

출력

1부터 S(추 무게의 합) 사이에 있는 정수 중, 양팔 저울을 한번만 이용해서는 측정이 불가능한 경우의 수를 출력한다.

 

******************************************************************************************************************************

 

2629번 문제(https://www.acmicpc.net/problem/2629)와 이름도,풀이도 비슷한 문제입니다. 정해는dp문제이고

이 문제또한 dp로 풀 수 있지만 브루트포스 풀이를 적어볼까합니다. 이 문제는 시간초과를 1번 받았는데,

약간의 최적화 및 전처리로 맞았습니다를 받을 수 있었습니다. 그 과정을 소개하자면..

처음 접근은 왼쪽 저울과 오른쪽 저울을 나눠서, 모든 추를 놓는 경우의 수를 계산하였습니다.

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
const int INF=987654321,MAX_N=13+2;
int N,arr[MAX_N],sum=0,ans=0;
bool visited[MAX_N*200000]={0,};

int main()
{
    cin>>N;
    for(int i=0;i<N;i++){cin>>arr[i],sum+=arr[i];}
    
    for(int left=0;left<(1<<N);left++)
        for(int right=0;right<(1<<N);right++)
    {
        int tmp=0;
        //왼쪽 추는 합계에 더한다.
        for(int i=0;i<N;i++)if(left&(1<<i))tmp+=arr[i];
        //오른쪽 추는 합계에 뺀다.
        for(int i=0;i<N;i++)if(right&(1<<i))tmp-=arr[i];
        visited[abs(tmp)]=true;
    }
    for(int i=1;i<=sum;i++)if(!visited[i])ans++;
    cout<<ans;
}

1여기서 코드의 논리적인 오류를 지적할 수 있습니다. left와right변수가 둘다 i번째 추를 사용하는 경우가 생길 수 있는데, 둘 다 i번째 추를 사용하면 left를 더하고 right를 빼는 과정에서 i번째 추를 둘 다 사용하지 않는 것과 같은 경우가 되어버립니다. 따라서 답은 올바르게 나오게됩니다. 하지만 이 코드는 시간초과를 받는 코드입니다.

시간복잡도를 계산해보면, 2중for문의 복잡도가 각각 2^N이고 그 안에서 또 2N만큼의 반복문을 돕니다,

따라서 O((2^N)^2*N)의 복잡도가 나오게되는데, N의 제한이 13이므로 (2^13)^2*13=약 9억만큼의 계산을 하게되지만 빅오계산법에서 *2가 생략되었으므로 18억 정도의 계산을 하게되어 1초만에 답을 내기엔 빠듯합니다. 시간을 더 줄이려면 어떻게 해야할까요? 2중for문 안에서 돌고있는 2*N만큼의 저 반복문을 약간의 전처리를 통해 시간복잡도를 줄일 수 있습니다. 밑에 새로운 정답코드가 있습니다.

#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
const int INF=987654321,MAX_N=13+2;
int N,arr[MAX_N],sum=0,bits=0,ans=0;
bool visited[MAX_N*200000]={0,};
int leftCache[(const int)pow(2,MAX_N)]={0,},rightCache[(const int)pow(2,MAX_N)]={0,};

int main()
{
    cin>>N;
    for(int i=0;i<N;i++){cin>>arr[i],sum+=arr[i];}

    for(int left=0;left<(1<<N);left++)
        for(int i=0;i<N;i++)if(left&(1<<i))leftCache[left]+=arr[i];
    for(int right=0;right<(1<<N);right++)
        for(int i=0;i<N;i++)if(right&(1<<i))rightCache[right]+=arr[i];

    for(int left=0;left<(1<<N);left++)
        for(int right=0;right<(1<<N);right++)
    {
        int tmp=leftCache[left]-rightCache[right];
        visited[abs(tmp)]=true;
    }
    for(int i=1;i<=sum;i++)if(!visited[i])ans++;
    cout<<ans;
}

leftCache와rightCache 저장공간을 만들어 left와right변수와 대응하는 값들을 미리 저장해 두었습니다.

이 코드의 시간복잡도는 O((2^N)*(2^N+N))으로 1초의 시간제한을 넉넉히 통과할 수 있습니다.

한국정보올림피아드 중등부 문제인데, KOI문제를 풀면 풀수록 대체 중학생이 이걸 어떻게 푸나 생각이 듭니다.

특히 이 다음문제인 17611번 직각다각형 문제를 풀면서 더더욱 느꼈는데, 다음 포스팅에 풀이를 적으려 합니다.