[백준] 2003번 수들의 합 2

 

 

문제

소스코드

#include<iostream>
#include<vector>
 
constexpr long long max_n = 1001;
constexpr long long  max_m = 300000001;
/*
1. 왼쪽 오른쪽 0
2. 현재 부분합 m이 같다면 ++카운터
3. 현재 부분합이 m보다 작거나 같다면 ++오른쪽
4. 현재 부분합이 m보다 크다면 ++왼쪽
5. 모든 경우를 확인할 때까지 2~4반복
*/
int twopointer(long long m, std::vector<long long>& v) {
 
    long long leftpointer{}, rightpoint{};
    long long result{};
    long long sum{};
 
    while(leftpointer<v.size()) {
 
        // sum이 m보다 작으니까 계속  right 증가시켜보자
        while (sum<m  && rightpoint<v.size()){
            sum += v[rightpoint];
            ++rightpoint;
        }
 
        //같으면 결과 증가
        if (sum == m)
            ++result;
        sum -= v[leftpointer];
        ++leftpointer;
    }
    return result;
}
 
int main() {
    long long n{}, m{};
    std::cin >> n >> m;
    std::vector<long long> v;
    for (long long i = 0; i < n; ++i) {
        long long number{};
        std::cin >> number;
        v.emplace_back(number);
    }
    std::cout << twopointer(m, v) << "\n";
}
 

 

 

후기

이 문제를 해결하기 위한 키워드는 Two Pointer이다.

 

Two Pointer는 배열에서 특정 구간의 합을 구하자고 할 때 O(N) 시간 안에 문제를 풀 수 있는 알고리즘이며 두 개의 포인터를 사용한다고 해서 Two Pointer라고 불리며 자세한 알고리즘의 설명은 밑에 유튜브 링크를 참고하면 좋다.

 

Two Pointer를 이용해서 문제를 풀어보았다. 원리만 듣고 직접구현했는데 잘 안돼서 밑에 유튜브 링크에서 설명을 듣고 

동일하게 작성해서 문제를 풀었기 때문에 본인실력으로 풀었다 보기는 어렵다. Two Pointer는 알고리즘 코딩 테스트에서도

자주 출제된다고 하니 배워두는게 좋다고 본다.

 

출처 및 레퍼런스

문제 링크: www.acmicpc.net/problem/2003

알고리즘 유튜브 링크: youtu.be/rI8NRQsAS_swww.youtube.com/watch?v=rI8NRQsAS_s