[백준] 3273 두 수의 합

문제 설명

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

3273번: 두 수의 합

n개의 서로 다른 양의 정수가 주어지고, 자연수 x가 주어졌을 때

a[i] + a[j] = x인 쌍의 수를 구하기

 

문제 풀이법

단순히

for(int i = 0; i < n; i++)
{
	for (int j = i + 1; j < n; j++)
    {
    	if (arr[i] + arr[j] == x)
        	cnt++:
     }
}

했다가는 시간초과 난다 (해봤다)

 

투포인터 알고리즘을 통해 문제를 해결해야한다

 

투포인터 알고리즘이란?

• 리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘

 

 

이 문제를 풀기 위해서는 

• 오름차순으로 정렬하기
• right와 left의 위치 잡기 (right는 0으로, left는 n - 1)로 설정
• v[right] + v[left] < x 일 때는 right++ 하기
• v[right] + v[left] > x 일 때는 left-- 하기
• v[right] + v[left] == x일 때는 cnt++, right++, left-- 하기
• right < left 때는 종료

 

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> v;
    
    int tmp;
    for (int i = 0; i < n; i++)
    {
        cin >> tmp;
        v.push_back(tmp);
    }
    
    int x;
    cin >> x;
    
    int cnt = 0;
    
    sort(v.begin(), v.end());
   
    int right = 0;
    int left = n - 1;
    
    while (right < left)
    {
        if (v[right] + v[left] < x)
            right++;
        else if (v[right] + v[left] > x)
            left--;
        else 
        {
            cnt++;
            left--;
            right++;
        }
        
    }
    printf("%d\n", cnt);
    
    return 0;
}