[BOJ/백준][Gold3] 1253 : 좋다 (C++)

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

1253번: 좋다

 

[난이도] Gold3
[유형] 자료구조

[풀이]
GOOD인 수는 set에 저장한다.
2중으로 모든 pair를 확인하면서 set에 만들 수 있는 수를 저장한다.
이때 주의할 것이
a[i]=0, a[j]=3 이런 경우에 set에 3을 그냥 넣으면 안된다.
왜냐하면 0+3으로 3은 자기 자신을 포함해서 만들어진 수이므로 GOOD인 수가 아니다.
이 경우를 제외하기 위해 일단 a[i] 또는 a[j]가 0인 경우는 제외하고 set에 저장해준다.

0과 관련하여 나올 수 있는 예외를 생각해보면 다음과 같다.

case 1) 0+3과 같이 자기 자신을 포함했지만 3이 GOOD인 수이려면 수열에 3이 2개 이상 있으면 된다. (ex 0,3,3)
case 2) 0이 GOOD인 수이려면 (-3)+3 이런 식의 수가 존재하여 위의 루프에서 set에 추가되거나, 0끼리의 합으로 GOOD인 수를 만들어야 한다. 이때, 0이 2개만 있게 되면 자기 자신을 포함하여 0을 만든 것이기 때문에 GOOD인 수가 될 수 없고,
0이 3개 이상 있어야 한다.

위의 예외 처리를 위해서 map을 이용해 a 배열의 각 원소가 개수가 몇개씩 있는지를 counting해서 저장해주었다.
case 1을 처리하기 위해 => map[0]이 3 이상이면 0을 set에 넣어주고.
case 2를 처리하기 위해 => map[0]이 1 이상이고, 현재 확인중인 원소 A가 2개 이상이면 A를 set에 넣어준다.

이제 set에는 GOOD인 수가 모두 저장되게 되었으므로 답을 출력해주면 된다.

 

#include <cstdio>
#include <map>
#include <set>
using namespace std;
int N,a[2000];
map<int,int> cnt;
int main(){

    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    set<int> s;
    for(int i=0;i<N-1;i++){
        cnt[a[i]]++;
        for(int j=i+1;j<N;j++) {
            if(a[i]!=0&&a[j]!=0) s.insert(a[i]+a[j]);
        }
    }
    cnt[a[N-1]]++;
    for(auto v : cnt){
        if(v.first==0) {
            if(v.second>2) s.insert(0);
        }else{
            if(cnt.find(0)!=cnt.end() && v.second>1) s.insert(v.first);
        }
    }

    int ans=0;
    for(int i=0;i<N;i++) {
        if(s.find(a[i]) !=s.end()) {
            ans++;
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/1253.cpp