[BOJ 2003] 수들의 합 2 (C++)

수들의 합 2 (Silver 3)

문제

전체 문제 보기

2003번: 수들의 합 2

접근법

이 문제는 투 포인트 알고리즘의 기본 문제에 해당합니다. 전체 수열이 있을 때 왼쪽 포인터와 오른쪽 포인터 변수를 만듭니다. 그리고 현재 총 합 sum 이 M보다 작다면 오른쪽 포인터를 오른쪽으로 한 칸 이동시키고, sum이 M보다 크다면 왼쪽 포인터를 오른쪽으로 한칸 이동시키면서 문제를 풀 수 있습니다.

처음 left 포인터와 right 포인터는 0번째 인덱스를 가리킵니다. sum의 값이 M보다 작기 때문에 right가 가리키는 값을 sum에 더한 후 right를 오른쪽으로 옮깁니다.

 

 

sum이 2 증가했지만 아직 M보다 작기 때문에 right가 가리키는 값을 sum에 더한 후 한 칸 더 옮깁니다.

 

 

sum이 1 증가해서 3이 되었지만 아직 M보다 작기 때문에 한번 더 right가 가리키는 값을 sum에 더한 후 한 칸 더 옮깁니다.

 

 

이제 sum의 값이 M과 같아졌습니다. 이제 answer 카운트를 1 증가 시킵니다. 이제 다음 경우를 계속 탐색하기 위해서 left가 가리키고 있는 값을 sum에서 뺀 후 left를 오른쪽으로 한 칸 이동시킵니다.

 

 

다시 sum에 M보다 작아졌기 때문에 right가 가리키고 있는 값을 sum에 더한 후 right를 한 칸 더 이동시킵니다.

 

 

이번에는 sum이 M보다 더 커졌습니다. left가 가리키고 있는 값을 sum에 뺀 후 left를 오른쪽으로 이동시킵니다.

 

 

이번에는 sum이 M과 같은 값이 되었습니다. 문제에서 찾고 있는 경우입니다. answer 카운터를 1 증가시킵니다. 이런 식으로 right 전체 배열의 크기와 같아질 때까지 반복하여 답을 구할 수 있습니다. 

전체 구현

#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;


int main()
{
    //입출력 성능향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    int N, M; // N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)
    cin >> N >> M;
    vector<int> A(N);
    for (int& a : A)
    {
        cin >> a;
    }
    int sum{};
    int left{}, right{};
    int answer{};

    while (true)
    {
        if (sum >= M)
        {
            sum -= A[left];
            left++;
        }
        else if (sum < M)
        {
            if (right == A.size()) break;
            sum += A[right];
            right++;
        }

        if (sum == M) answer++;
    }

    cout << answer;
    return 0;
}

성능 평가

while문 내에서 전체 수열의 원소를 한 번씩 sum에 더하거나 빼기 때문에 전체 시간 복잡도는 \(O(N)\)입니다. 공간 복잡도 또한 전체 데이터를 저장할 배열이 필요하기 때문에 \(O(N)\) 입니다.