[C++] 백준 3273 문제 해설

3273번: 두 수의 합

 

요즘 머리를 좀 안 쓴것 같아서 오늘부터 백준을 한 문제씩 풀어보려 한다. (안되면 말고)

처음으로 시도해 본 문제는 비교적 쉬운 투포인터 문제이다.

 

 

처음볼땐 언어적으로 이해하기가 힘들어서

그냥 코드를 먼저 살펴보니 쉽게 이해가 되었다.

 

 

설명

입력 3개를 받는다.

첫 입력 = 받을 수열의 size

두번째 입력 = ' ' 로 구분지은 수열

세번째 입력 = 수열중 2개를 더해서 나와야 되는 숫자.

 

'n개의 서로 다른 양의 정수' 를 입력 받는다 했으므로, 수열 내의 숫자는 모두 다르다.

그 숫자들 중에서 아무거나 다른거 2개 집어서 더했더니 '세번째 입력' 된 숫자가 나오면 정답이다.

기본적으로 이진탐색 을 생각하긴 쉬우나, 여기선 덧셈이 들어가므로 아주 조금 창의적 생각이 필요하다.

 

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main() 
{
    ios_base::sync_with_stdio(false);
 
    int nums, standard;
    vector<int> v_arr;
    int cnt = 0;
 
    cin >> nums;
    int temp;
 
    for (int i = 0; i < nums; i++) 
    {
        v_arr.push_back(temp);
    }
 
    cin >> standard;
    sort(v_arr.begin(), v_arr.end());
    
    int start = 0;
    int end = v_arr.size() - 1;
 
    while (true)
    {
        if (start >= end)
            break;
 
        int sum = v_arr.at(start) + v_arr.at(end);
        
        if (sum == standard)
        {
            ++cnt;
            --end;
            ++start;
        }
        else if (sum > standard)
        {
            --end;
        }
        else
        {
            ++start;
        }
    }
 
    std::cout << cnt;
}

 

sort 부분까지는 설명이 딱히 필요하지 않다고 생각되므로 패스,

초보자를 위해 sort 를 왜 하는지 설명하자면

이진 탐색 문서를 참조해 봐라.

해당 문제와 완벽히 일치하진 않으나, sort 하는 이유는 같다.

sort 를 해 줘야 탐색시간이 줄어든다.

 

 

while(true) 부분 코드는 매우 쉽다.

배열 자체가 겹치는 숫자가 없고, sort 되어 있으므로, start, end 지점 양 끝단에서

start 지점 인덱스는 올리고, end 지점은 하나씩 내려가면서 비교한다.

 

여기서 올리고, 내리고의 기준은

sum 이다.

더했을때 3번째 입력값(standard) 보다 크다면 == end를 내려 sum 값을 낮추고

3번째 입력값(standard) 보다 작다면 == start 값을 올린다.

 

standard 와 같은 숫자가 발견된다면, end--, start++ 를 해 준다.

아까 말했듯 겹치는 숫자가 없기때문에 가능하다.

 

끝.

 

개인적으로 std::tie(null) 의 경우는

ms 단위로 체크시에 특별히 쓰고 안쓰고의 run 시간차이가 없어서 이용하지 않는다.