Memo
로직 설명
•
시작 포인터는 첫 번째 인덱스부터 시작합니다.
•
왼쪽 포인터는 원하는 값보다 현재 누적해온 값 보다 작은 합을 만들고 싶으면 증가시키고, 오른쪽 포인터는 원하는 값보다 현재 누적해온 값 보다 큰 합을 만들고 싶으면 증가시킵니다. (시간 복잡도 : O(N))
자료 구조
•
array
코드 설명
while (right != N)
{
if (sum_val == M)
ans++;
if (sum_val > M)
{
sum_val -= A[left];
left++;
}
else
{
right++;
sum_val += A[right];
}
}
C++
복사
•
"i번째 수부터 j번째 수까지의 합"에 초점을 맞춰봅니다.
•
오른쪽 포인터를 증가시켜 가며, 왼쪽 포인터와 오른쪽 포인터 사이 값들의 합이 M보다 크거나 같아질 때까지 증가시킵니다.
•
M과 크기가 같아지면 count를 세줍니다.
•
만약 왼쪽 포인터와 오른쪽 포인터 사이 값들의 합이 M보다 커지면, 왼쪽 포인터를 증가시킵니다.
•
왼쪽 포인터를 증가시키면, 그 사이의 값들은 이전 값보다 무조건 작습니다.
어려웠던 부분 
•
투 포인터를 어떻게 적용할 것인지. 정렬을 하면 안되는데 계속 집착함.
개선할 부분
•
문제를 정확하고 빠르게 이해하기.
Code
제출 날짜
@3/30/2021
메모리
2056 KB
시간
0 ms
#include <iostream>
int N, M;
int A[10002];
int ans;
void input_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
input_faster();
std::cin >> N >> M;
for (int i = 0 ; i < N ; i++)
std::cin >> A[i];
}
void solve()
{
int left, right;
left = 0;
right = 0;
int sum_val = A[0];
while (right != N)
{
if (sum_val == M)
ans++;
if (sum_val > M)
{
sum_val -= A[left];
left++;
}
else
{
right++;
sum_val += A[right];
}
}
}
void print_val()
{
std::cout << ans;
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사
