문제 링크입니다: https://www.acmicpc.net/problem/2003
투 포인터 알고리즘을 적용하면 쉽게 풀 수 있는 문제였습니다.
시간 제한이 0.5초이기 때문에 O(N^2)으로 풀면 안되고 low와 high를 적절히 선정하여 O(N^2)보다 빠르게 풀어야합니다.
알고리즘은 아래와 같습니다.
1. low가 high 이하이고 high가 N 미만일 때 아래와 같은 상황을 계속 확인해줍니다.
i)구간 합이 M보다 작다면 high를 하나 더 오른쪽으로 가고 해당 숫자도 구간 합에 더해줍니다.
ii)구간 합이 M과 같다면 경우의 수를 늘려주고 high를 하나 더 오른쪽으로 가고 해당 숫자도 구간 합에 더해줍니다.
iii)구간 합이 M보다 크다면 low를 하나 더 오른쪽으로 가주고 low 위치에 있던 숫자를 sum에서 빼줍니다.
a)이 때, low가 high를 역전하고 low가 N 미만일 경우 while문의 조건을 맞추기 위해 high를 low 위치와 같게 만들고 구간을 low에서부터 다시 시작합니다.
#include <iostream>
using namespace std;
const int MAX = 10000;
int arr[MAX];
int main(void)
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
for (int i = 0; i < N; i++)
cin >> arr[i];
int low = 0, high = 0;
int sum = arr[0];
int result = 0;
//투 포인터 알고리즘 적용
while(low <= high && high < N)
{
if (sum < M)
sum += arr[++high];
else if (sum == M)
{
result++;
sum += arr[++high];
}
else if (sum > M)
{
sum -= arr[low++];
//low가 high를 역전하면 low에서부터 다시 시작
if (low > high && low < N)
{
high = low;
sum = arr[low];
}
}
}
cout << result << "\n";
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 1644번 소수의 연속합 (0) | 2019.01.27 |
---|---|
백준 1806번 부분합 (4) | 2019.01.27 |
백준 9576번 책 나눠주기 (0) | 2019.01.27 |
백준 2831번 댄스 파티 (0) | 2019.01.26 |
백준 2828번 사과 담기 게임 (0) | 2019.01.26 |