[BOJ/C++] 1253번 문제풀이

문제 설명

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

---

풀이 과정

우선 해당 문제를 설명하면 다음과 같이 요약할 수 있다.

 

n개의 숫자가 주어지고, n개의 숫자 내에서 i번째 숫자가 서로 다른 두 숫자를 합쳐 나타낼 수 있다면 해당 i번째 숫자는 좋은 수 이다. 좋은 수의 갯수를 출력해보자. 이때, i번째 숫자를 서로 다른 두 숫자의 합으로 나타낼 때, i번째 숫자는 포함시켜서는 안된다.

 

이 문제에서 사용되는 알고리즘은 '이분탐색'이라고 한다.

이분 탐색

이진 탐색이라고도 부르는 이분 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘으로 이진 탐색의 과정은 다음과 같다.

 

▶ 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다.

 

이진 탐색과 관련된 설명을 참고하여 C++ 언어로 코드를 작성해보았다

자세한 코드에 대한 설명은 주석을 통해 간단하게 달아두었다.

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0, ans = 0;
    cin >> n;
    vector<int> v(n);
    
    for(int i=0; i<n; i++) cin >> v[i];
    // 백터에 n개의 숫자를 입력받고 오름차순으로 정렬해준다.
    sort(v.begin(),v.end()); 
    
    // n개의 숫자만큼 for문을 돌린다.
    for(int i=0; i<n; i++){
        int l=0, r=n-1; // l=0, r=n-1로 초기값을 두고 시작한다.
        
        // l<r의 조건일때까지만 while문을 돌린다
        while(l<r){
            // 만약 l==i이거나 r==i일 경우, 서로 다른 두 숫자의 합으로 나타낼 때, i번째 숫자는 포함시켜선 안된다는 규칙을 지키지 못한다.
            // l==i일 경우 l++을 하고, r==i일 경우 r--를 한다.
            if(l==i){l++; continue;}
            if(r==i){r--;continue;}
            
            // 만약 v[i] > v[l]+v[r]일 경우, l++을 한다.
            if(v[i]>v[l]+v[r]) l++;
            
            // v[i] == v[l]+v[r]일 경우 정답을 찾았으니 ans를 +1하고 break한다.
            else if(v[i]==v[l]+v[r]){
                ans++;
                break;
            }
            else r--; // v[i] < v[l] + v[r]일 경우, r--을 한다.
        }
    }
    cout << ans << "\n"; // 최종적으로 정답을 출력한다.
    return 0;
}

 

 

[참고자료]

https://astrid-dm.tistory.com/m/470

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search