백준 #1253 좋다

이 문제는 처음에 Gold III로 난이도가 설정되어 있어서 왜 이렇게 높지 했습니다.  정답률도 20.8%로 낮아서, 정답률도 상당히 낮네하면서 설마하고 제출했는데, 틀렸습니다가 나오네요.  

 

Good Number!

N 개의 수가 주어지는데, 자신을 제외한 다른 두개의 수의 합으로 자신이 이루어지면, 이 수의 개수를 출력하는 문제입니다.

 

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

1253번: 좋다

가장 편하게 생각하는 것은 두개의 수 조합으로 set 자료형에 넣고서, 수가 이 set에 있는지 검사하는 방법입니다.

첫번째 틀리는 경우는 0인 수가 있는 경우입니다.  0이 들어오면, 자기자신과 0을 합하면 자기 자신이 되므로 항상 set에 있게 됩니다.

두번째 틀리는 경우는 0인 수가 있고, 자기 자신과 같은 수가 또 존재하는 경우입니다.

세번째 틀리는 경우는 0인 수가 다수개 있는 경우입니다.

 

이 세가지 예외를 적절하게 처리하는 방법을 택하여야 하는데, 그게 꽤 귀찮습니다.  전 0의 갯수를 세고, 이 수에 의해서 만들어지는 자기 자신 수를 제거하는 방법을 택했습니다.  알고리즘으로는 \(O(N^2\) 입니다.

 

예외가 나올 수 있는 경우를 해보면요.

 

3
0 1 2
==> 0

3
0 1 1
==> 2

3
0 1 -1
==> 1

4
0 1 1 2
==> 3

5
0 0 0 1 1
==> 5

5
0 0 0 1 2
==> 3

 

저는 map 자료형을 사용해서 똑같은 결과가 몇번 나오는 가 검사했습니다.  0의 개수를 따로 세어두었기 때문에 map 자료형에서 나온 조합된 값들의 수에서 0의 개수를 빼면 자연스럽게 0과 자기 자신 수가 참여한 수의 개수가 빠집니다.  자기 자신이 0인 경우에는 예외처리를 했습니다.  0이 3개라면, 여기서 조합되는 0의 개수는 3이 됩니다.  하지만, 자기 자신이 0이기 때문에 이 중 2개만 자기 자신과 결합한 조합 수가 됩니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------
//  baekjoon #1253 - Good
//    - by Aubrey Choi
//    - created at 2020-01-12
//----------------------------------------------------------
#include <stdio.h>
#include <unordered_map>

int abs(int n) { return n<0?-n:n; }
int main()
{
  int v[2000], n, i, j, s, cnt=0, z=0;
  std::unordered_map<int,int> map;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",v+i),z+=(v[i]==0);
  for(i=0;i<n-1;i++) for(j=i+1;j<n;j++)
  {
    s=v[i]+v[j];
    if(abs(s)<=1000000000) map[s]++;
  }
  for(i=0;i<n;i++)
  {
    if(map.find(v[i])==map.end()) continue;
    s = map[v[i]]-z+(v[i]==0);
    if(s) cnt++;
  }
  printf("%d\n",cnt);
}