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

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

[문제 풀이 사이트]

2003번: 수들의 합 2

[문제 설명]

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

[입력]

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

[출력]

첫째 줄에 경우의 수를 출력한다.

[입출력 예]

입력	출력
4 2 1 1 1 1	3
10 5 1 2 3 4 2 5 3 1 1 2	3

[문제 풀이]

입출력예 1을 예를 들어 설명하도록 하겠다.

2개의 start, end 변수를 사용한다.
처음에 start와 end 변수는 배열의 첫번째 원소(인덱스 0)을 가리키도록 한다.
그리고 현재까지의 sum은 1이 된다.

i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 2가 되는 경우의 수를 구해야하기 때문에 end 변수를 오른쪽으로 이동시킨다.
end를 이동하며 sum값을 계산하고 sum(2)을 M(2)와 비교한다.
비교했을 때 sum값이 M값과 같으므로 경우의 수를 1 증가시킨다.

sum값과 M값이 같을 때를 찾았으므로 start 변수를 오른쪽으로 이동시킨다.
start 변수가 이동하였기 때문에 sum값 또한 변경이 된다.

위에서 수행했던 과정을 똑같이 반복한다.
i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 2가 되는 경우의 수를 구해야하기 때문에 end 변수를 오른쪽으로 이동시킨다.
end를 이동하며 sum값을 계산하고 sum(2)을 M(2)와 비교한다.
비교했을 때 sum값이 M값과 같으므로 경우의 수를 1 증가시킨다.

다음 과정도 위 과정과 동일하게 반복한다.
입출력 예1에서 구할 수 있는 경우의 수는 3이다.

[최종 코드]

[GitHub]

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

#include <bits/stdc++.h>
using namespace std;
vector<int> gNum;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M; cin >> N >> M;
    for(int i = 0; i < N; ++i) {
        int num; cin >> num;
        gNum.emplace_back(num);
    }
    int en = 0;
    int cnt = 0;
    int sum = gNum[0];
    for(int st = 0; st < N; ++st) {
        while(en < N && sum < M) {
            en += 1;
            sum += gNum[en];
        }
        if(en == N) break;
        if(sum == M) {
            cnt += 1;
            sum -= gNum[st];
        } else if(sum > M) {
            sum -= gNum[st];
        } else {}
    }
    cout << cnt;
    return 0;
}