취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2003번 문제인 수들의 합 2이다.
문제는 아래 링크를 확인하자.

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

현재 살펴보고 있는 구간을 [L,R]이라 할 때, sum[L,R]이 목표하는 값보다 작다면 R을 하나 늘리고 크다면 L을 하나 늘리며 같다면 계수하는 시뮬레이션을 돌려 문제를 해결하자.

매 단계마다 sum[L,R]을 새로 계산하지 않고 이전 단계에서 구한 합에 구간이 바뀌면서 더해지는/빠지는 값만을 연산하는 것으로 프로그램의 실행시간을 절약할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, M;
int arr[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	int cnt = 0;
	int L = 0, R = 0, val = arr[0];
	while (R < N) {
		if (val == M) {
			cnt++;
			val += arr[++R];
			val -= arr[L++];
		}
		else if (val < M) val += arr[++R];
		else val -= arr[L++];
	}

	cout << cnt;
}