뚝딱뚝딱

https://www.acmicpc.net/problem/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을 넘지 않는 자연수이다.

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

수열에서 연속적인 값들의 합이 M과 같은 경우의 수를 구하는 문제이다.

✅ 문제 풀이

• 일단 누적합을 나타내는 sum에는 수열에서 첫번째 값을 넣어두고 시작한다.
• 실행시간 조건이 0.5초이기 때문에, for문에 의한 순회는 한번을 최대로 해야 한다.
• 그럼 부분 합을 어떻게 구할 수 있을까?
• 두 포인터를 이용해서, 시작 지점과 끝 지점을 가리키도록 한다.
• 그것을 각각 s와 e로 하고, 수열의 인덱스를 가리키도록 한다.
• 처음에는 s와 e를 0으로 시작한다. 따라서 sum도 수열의 첫번째 값만을 담고 있어야 한다.
• 그렇게 해서 s<=e를 만족하는 한 계속 경우의 수를 찾아갈 것이다.
• if문을 통해 현재의 sum값과 M을 비교한다.
• 만약 sum이 M보다 작으면, 더 더해주어야 하기때문에 e를 하나 늘리고, 현재 e가 가리키는 값을 sum에 더해준다.
  이때 주의할 점은, 하나 늘어난 e가 N을 넘지 않아야 한다는 것이다. N을 넘지 않았을 경우에만 e가 가리키는 값을 sum에 더해주면 된다.=>유효성을 확인하는 부분이다.
• 만약 sum이 M과 같다면, 하나의 경우가 되는 것이므로, 경우의 수를 카운트하는 answer를 하나 늘려준다.
  그리고 수열의 모든 값은 자연수이기 때문에, s를 늘리면 값을 줄고, e를 늘리면 값이 늘어나게 되는 건 분명하다. 따라서 이 경우에는 s와 e를 둘다 하나씩 늘리도록 한다.
• 만약 sum이 M보다 크다면, 빼주어야 하기때문에, sum에서 현재 s가 가리키는 값을 빼준다.
  그리고 여기서 주의할 점이 있다.
  만약 s가 e와 동일했었다면 다음 값을 sum에 넣어주어야 하기 때문에, s와 e를 둘다늘리고, 이 둘이 가리키는 값을 sum에 넣어주도록 한다.
  s와 e가 동일하지 않았다면 s를 하나 늘려주면 된다.
• 그리고 for문을 다 순회한 후에는 answer를 출력해주면 된다. 

☑ 코드 전문

#include<iostream>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

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

	int sum = arr[0];
	int answer = 0;
	for (int s = 0, e = 0; s <= e;) {
		if (sum < M) {
			e++;
			if (e < N) sum += arr[e];
			else break;
		}
		if (sum == M) {
			answer++;
			sum -= arr[s];
			s++;
			e++;
			if (e < N) sum += arr[e];
			else break;
		}
		if (sum > M) {
			sum -= arr[s];
			if (s == e && e < N - 1) {
				s++;
				e++;
				sum += arr[e];
			}
			else {
				s++;
			}
		}
	}

	cout << answer;
}