[백준] 1940번 : 주몽

---

🔗문제 링크

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

1940번: 주몽

👩‍💻코드

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

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N;
    int M;
    vector<int> numbers(N,0);
    
    cin >> N;
    cin >> M;
    
    for (int i=0; i<N; i++){
        int number;
        cin >> number;
        numbers.push_back(number);
    }
    
    sort(numbers.begin(), numbers.end());
    
    int start_index = 0;
    int end_index = N-1;
    int count = 0;
    
    while (start_index < end_index){
        int sum = numbers[start_index] + numbers[end_index];
        
        if(sum == M){
            count++;
            start_index++;
            end_index--;
        }else if(sum < M){
            start_index++;
        }else{
            end_index--;
        }
    }
    
    cout << count << "\n";
}

✏️풀이

Do it! 알고리즘 코딩테스트 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

이전 문제에서의 풀이법과 동일하게 투 포인터라는 알고리즘을 사용합니다.

 

먼저 투 포인터로 비교할 수 있도록 주어진 재료들 값을 오름차순으로 정렬해줍니다.

정렬 후 start_index는 앞에서부터, end_index는 뒤에서부터 위치합니다.

 

두 포인터의 합이 m보다 작거나 크면 start_index를 하나 뒤로 옮기거나 end_index를 하나 앞으로 옮깁니다.

정답인 경우는 두개의 포인터를 모두 움직입니다.