본문 바로가기
Algorithm/Baekjoon

2003_수들의 합 2

by 모너아링 2023. 1. 2.

▶실버4

풀이

투 포인터를 이용한 문제. 같은 방향으로 L, R가 나아가는 형태이다. 먼저 L과 R은 모두 인덱스 0번째를 가리킨다.

A[L] ~ A[R]의 합인 sum이 m보다 작다면 sum의 값을 늘려야하므로 R을 오른쪽으로 한 칸 이동하고,

sum이 m보다 크다면 sum의 값을 줄여야하므로 L을 오른쪽으로 한 칸 이동한다.

sum == m인 경우는 R, L 모두 오른쪽으로 한 칸 이동한다. 

R이 N을 벗어나기 전까지 진행한다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int A[10001];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int l = 0, r = 0;
	long long n, m;
	int ans = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> A[i];
	}
	long long sum = A[0];
	while (1) {
		if (sum < m) {
			r++;
			if (r >= n) {
				break;
			}
			sum += A[r];
		}
		else if (sum > m) {
			sum -= A[l];
			l++;
		}
		else {
			ans++;
			sum -= A[l];
			l++;
			r++;
			if (r >= n) {
				break;
			}
			sum += A[r];
		}
	}
	cout << ans;
}

 

'Algorithm > Baekjoon' 카테고리의 다른 글

11055_가장 큰 증가 부분 수열  (0) 2023.01.10
11057_오르막수  (0) 2023.01.04
21921_블로그  (0) 2023.01.01
2583_영역 구하기  (0) 2022.11.11
3184_양  (0) 2022.11.10