# 3273. 두 수의 합

관련 알고리즘 : 배열

 

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

3273번: 두 수의 합

---

문제 풀이

 시간복잡도를 계산하는 능력이 타 친구들에 비해 현저하게(...) 떨어지는 것 같아 관련 문제를 들고왔다.

처음에는 내가 평소에 짜던 것처럼 이중for문을 돌며 모든 경우를 검사하게 했지만 역시나! 시간 초과 오류가 뜨게 되었다.

어찌보면 당연하다. 수의 범위가 (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 이기 때문에...

 

구현 방법을 생각해내는데 은근 헷갈렸다.

우선 시간복잡도를 O(N) 정도로 만들기 위해서 이중for문을 통해 구현하는 방법을 배제하였다.

 

📍고려사항

1. 2개의 수의 합이 x이고, a_(i)와 a_(j)에서 i와 j는 서로 값이 다르다.

2. 시간복잡도에 유의해야 한다.

 

예를 들어, x=12일 경우 (짝수일 때)

(1, 11) (2, 10) (3, 9) (4, 8) (5, 7) (6, 6) 의 경우가 있다.

이 때, (6, 6)의 경우는 같은 값이 2번 나오는 경우이므로 (5, 7)까지 생각해주도록 한다.

 

또한, x=13일 경우 (홀수일 때)

(1, 12) (2, 11) (3, 10) (4, 9) (5, 8) (6, 7) 의 경우가 있다.

 

따라서 for문을 돌 때,

- (1+x)/2 까지 돌면서,

- (x-i) 값이 입력받은 값에 있는지 여부를 검사해주면 된다.

 

---

c++코드

#include <iostream>

// 시간복잡도 주의 !!
using namespace std;

#define MAX 2000001

int n;
int arr[MAX];
int x;
int res = 0;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    int tmp;

    for(int i=0; i<n; i++)
    {
        cin >> tmp;
        arr[tmp] = 1; // 배열에 있는 숫자인지 여부
    }

    cin >> x;

    for(int i=1; i<(x+1)/2; i++)
    {
        if(arr[i]==1 && arr[x-i]==1) 
            res++;
    }

    cout << res;
    return 0;
}

 

실버3인데... 실버3도 이렇게 헷갈린다니...

알고리즘 공부 다시 해야겠다....