백준 2003번 수들의 합 2

문제 링크입니다: 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

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~