1253 좋다

문제 링크

• 내 풀이

전체 숫자를 순회중인 숫자의 인덱스 i, 다른 두 숫자를 가리키며 왼쪽에서 시작하는 인덱스 st와 오른쪽에서 시작하는 인덱스 ed를 투포인터 알고리즘을 활용하여 풀었다. 이분탐색을 이용하여 풀려고 했지만 두 수의 합을 이분탐색하는 아이디어가 떠올라지 않아 못했다. 정확히 이야기하면 합이 목적 값과 다른 경우 st, ed의 처리 방법을 어떻게 해야하는 지 모르겠다.

#include <iostream>
#include <algorithm>

using namespace std;

int N, n[2000];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> n[i];

    sort(n, n + N);
    
    int st, ed, sum, ret = 0;

    for (int i = 0; i < N; i++)
    {
        st = 0, ed = N - 1;
        while (st < ed)
        {
            sum = n[st] + n[ed];
            if (sum == n[i])
            {
                if (st != i && ed != i)
                {
                    ret++;
                    break;
                }
                else if (st == i)
                    st++;
                else if (ed == i)
                    ed--;
            }
            else if (sum >= n[i])
                ed--;
            else
                st++;
        }
    }

    cout << ret << "\n";
}

• 다른 풀이(바킹독님의 풀이)

2중 반복문을 이용하여 서로 다른 인덱스를 갖는 모든 수의 합을 만든 뒤 정렬하여 이분탐색하여 결과값을 찾는 풀이다. 생각보다 수행시간은 오래걸렸지만 아이디어는 습득해두자.

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;

int n;
int a[2004];
map<int,int> occur;
vector<int> add;
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a[i];
    occur[a[i]] += 1;
  }
  for(int i = 0; i < n; i++){
    if(a[i] == 0) continue;
    for(int j = i+1; j < n; j++){
      if(a[j] == 0) continue;
      add.pb(a[i]+a[j]);
    }
  }
  sort(add.begin(),add.end());
  int cnt = 0;
  for(int i = 0; i < n; i++){
    if(binary_search(add.begin(),add.end(),a[i])){
      cnt++;
      continue;
    }
    if(a[i] == 0){
      if(occur[0] >= 3){
        cnt++;
      }
      continue;
    }
    if(occur[0] >= 1 and occur[a[i]] >= 2){
      cnt++;
    }

  }
  cout << cnt;

}