이번 문제는 for문을 이중으로 사용하여 풀었다.

• 연속된 값들을 계속 더하여 cnt가 m과 같아지면 result를 증가시킨다.
• cnt가 m보다 작다면 계속 반복한다.

Code

#include <iostream>
#define MAX 10001
using namespace std;

int n, m;
int A[MAX];
int cnt=0;
int result=0;

void Input(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>A[i];
    }
}

void Solution(){
    for(int i=0; i<n; i++){
        cnt=A[i];
        if(A[i]==m){
            result++;
        }
        for(int j=i+1; j<n; j++){
            cnt+=A[j];
            if(cnt==m){
                result++;
            }
            else if(cnt<m){
                continue;
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    cout<<result<<endl;
    return 0;
}

문제는 풀었지만 알고리즘 분류에 두 포인터로 명시되어 있었고 두 포인터로 푸는 법도 찾아보았다.

• low, high로 두 포인터를 설정해준다.
• cnt의 크기에 따라서 low, high의 위치를 조정한다.
• high가 n보다 커지면 while문을 끝낸다.
• while문 안에서는 cnt가 m보다 커지면 low가 가리키는 값을 빼고, high가 가리키는 값을 더한다.
• 쉽게 말하면 low로 빼고, high로 더한다.

Code

#include <iostream>
#define MAX 10001
using namespace std;

int n, m;
int A[MAX];
int low=0, high=0;
int cnt=0;
int result=0;

void Input(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>A[i];
    }
}
void Solution(){
    while(1){
        if(cnt>=m)
            cnt-=A[low++];
        else if(high==n)
            break;
        else
            cnt+=A[high++];
        if(cnt==m)
            result++;
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    cout<<result<<endl;
    return 0;
}

이러한 문제는 두 포인터 알고리즘을 사용하면 시간이 단축된다는 사실을 알 수 있었다.