[BOJ] 3273: 두 수의 합

문제: https://www.acmicpc.net/problem/3273

 

 

 

 

: 처음 제출한 코드

#include <iostream>
#include <vector>
using namespace std;
int main()
{
  int n, x, result = 0;
  int arr[100000];
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  cin >> x;

  for (int i = 0; i < n - 1; i++)
    for (int j = i + 1; j < n; j++)
      (arr[i] + arr[j] == x) && result++;

  cout << result << '\n';
}

문제를 보자마자 시간복잡도 O(n²)인 풀이가 가장 먼저 떠올랐다.

수열 a를 arr 배열에 담고, 이중 반복문을 사용해서 a[i]와 a[j]를 더해가며 x와 같은 쌍이 나오면 result를 1증가시키는 방법으로 작성했다.

하지만 O(n²)이기 때문에 n의 크기가 커질수록 문제 해결에 걸리는 시간이 급격히 커지게 되면서 시간 초과됐다.

 

 

 

: 나중에 제출한 코드

#include <algorithm>
#include <iostream>
using namespace std;

int check[2000001] = {};
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int n, x, result = 0;
  int a[100000];
  
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    check[a[i]]++;
  }
  cin >> x;
  for (int i = 0; i < n; i++)
    if ((x > a[i]) && check[x - a[i]]) result++;
  cout << result / 2;
}

O(n²)으로는 해결할 수 없는 문제이기 때문에 O(n) 풀이를 생각해야 한다.

꽤 오랜시간 고민해봤지만 그럴듯한 아이디어 조차 떠오르지 않아서 바킹독의 풀이를 봤다.

바킹독은 occur이라는 배열을 선언하고 수열 값들의 존재 유무를 체크하는 용도로 사용했다.

바킹독의 풀이를 보고 나도 코드를 작성해봤다.

먼저 a 배열에 수열을 담고, check 배열에 1을 할당했다.

다음으로 a[i]가 x보다 작아야지만 합이 x가 되는 다른 짝을 찾을 수 있기 때문에 x > a[i]을 조건으로 걸어두고, check[x-a[i]]를 참조해서 합이 x가 되는 다른 짝이 존재하는지 체크한다.

존재한다면 result의 값을 1증가시켜준다.

이때 result는 a[i] = ai일 때랑 a[i] = aj일 때 각각의 짝이 2번 카운트된 것이기 때문에 중복을 없애기 위해 2로 나눠야 한다. 

 

 

 

: 수정한 코드

#include <algorithm>
#include <iostream>
using namespace std;
int a[100000];
bool check[2000001] = {};
int n, x;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int result = 0;
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  cin >> x;
  for (int i = 0; i < n; i++) {
    if (x > a[i] && check[x - a[i]]) result++;
    check[a[i]] = 1;
  }
  cout << result;
}

수정한 코드에서는 result를 2로 나누지 않는다.

애초에 중복으로 카운트를 하지 않기 때문이다.

합이 x를 만족하는 두 수를 (ai, aj)라고 할 때 a[i] = ai에서 aj가 check배열에 표시되지 않았더라도 a[i] = aj에서 ai가 check배열에 표시되어 있기 때문에 한 번만 카운트될 수 있기 때문이다.