Koala - 11기/코딩테스트 준비 스터디

[백준/C++] 2003번 : 수들의 합 2

_dudu 2023. 7. 30. 23:21

 

 

 

 

풀이

  • 누적합과 투포인터를 이용한다.
  • 왼쪽 포인터와 오른쪽 포인터를 설정하여 구간의 합을 계산한다. 
  • 구간의 합이 M과 같으면 경우의 수를 증가시키고 M보다 작으면 오른쪽 포인터를 증가시켜 구간을 확장하고 구간 합이 M보다 크면 왼쪽 포인터를 증가시켜 구간을 축소시킨다.
  • 오른쪽 포인터가 끝에 도달할 때까지 반복한다.
  • 시간복잡도 O(N)

 

 

 

코드

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

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    int count = 0; 
    int left = 0;  
    int right = 0; 
    int sum = A[0];

    while (right < N) {
        if (sum == M) {
            count++;
            sum += A[++right];
        } else if (sum < M) {
            sum += A[++right];
        } else {
            sum -= A[left++];
        }
    }

    cout << count << endl;

    return 0;
}

 

 

 

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

 

2003번: 수들의 합 2

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

www.acmicpc.net