백준 문제 3151번 합이 0 문제풀이 c++

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

3151번: 합이 0

 

문제해석

 

그냥 N이 최대 10000개이고 4초 제한이라 N^2으로 풀릴거같아서 별 생각 안하고 브루트포스 방법을 사용했다.

 

먼저 N개중에 2개를 뽑아서 더한 값을 x라고 하면 선택하지 않은 것중 -x가 있는지 없는지 확인했다.

 

코드에서 p는 양수 m은 음수이다.

예를들어 p[36]=2 이면 36이 2개란 뜻이고 m[24]=5 이면 -24가 5개란 뜻이다.

 

근데 귀찮게 이렇게 안하고 map 사용하면 되는데 작성할땐 이게 먼저 생각났나보다.

 

게다가 중복일때 경우의 수를 올리는 작업을 안해야 했는데

그거 안해도 시간안에 통과할것 같기도 하고 좀 어려워서 작성하지않았다.

 

때문에 같은 경우가 3!=6만큼 생기므로 최종답에서 6을 나누어주었다.

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
typedef long long int ll;
using namespace std;
void dfs(ll depth,ll sum);
bool visited[10005];
ll p[10005];
ll m[10005];
ll a[10005];
ll n;
ll ans=0;
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin>>n;
    for(ll i=0; i<n; i++)
    {
        cin>>a[i];
        if(a[i]>=0)
        {
            p[a[i]]++;
        }
        else
        {
            m[-a[i]]++;
        }
    }
    if(n<3)
    {
        cout<<"0\n";
    }
    else
    {
        dfs(0,0);
        cout<<ans/6<<"\n";
    }
}
void dfs(ll depth,ll sum){
    if(depth==2)
    {
        if(0<=abs(sum)&&abs(sum)<=10000)
        {
            if(sum>0)
            {
                ans=ans+m[sum];
            }
            else if(sum<0)
            {
                ans=ans+p[-sum];
            }
            else
            {
                ans=ans+p[0];
            }
        }
        return;
    }
    for(ll i=0; i<n; i++)
    {
        if(visited[i]==0)
        {
            if(a[i]>=0)
            {
                visited[i]=1;
                p[a[i]]--;
                dfs(depth+1,sum+a[i]);
                p[a[i]]++;
                visited[i]=0;
            }
            else
            {
                visited[i]=1;
                m[-a[i]]--;
                dfs(depth+1,sum+a[i]);
                m[-a[i]]++;
                visited[i]=0;
            }
        }
    }
}