[백준] 2003번 수들의 합 2

문제

https://www.acmicpc.net/problem/2003

풀이과정

1차원 배열에서 각각 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 기법인 투 포인터(two pointers) 문제다.

left ~ right 구간의 합을 확인하면 된다.

(93%,1초) 에서 “틀렸습니다”가 떴다. 왜 그런가 찾아봤더니 한 가지 예외처리를 해줘야되는 문제였다.

만약 left+1 이 right보다 커질 경우에는 left와 right의 자리를 바꿔줘야된다.

소스코드

#include <iostream>



using namespace std;



#define MAX_N 10001



int n, m;

int a[MAX_N];

int ans;



void solution()

{

    int left = 0, right = 0,now_Sum=a[0];



    while (left <= right && right < n)

    {

        // 현재 구간의 합이 m과 같을 경우 

        // right += 1

        if (now_Sum == m)

        {

            ans += 1;

            right += 1;

            now_Sum += a[right];

        }

        // 현재 구간의 합이 m보다 클 경우

        else if (now_Sum > m)

        {

            now_Sum -= a[left];

            left += 1;



            // left가 right보다 커진 경우 바꿔준다

            if (left > right && left < n)

            {

                right = left;

                now_Sum = a[left];

            }

        }

        // 현재 구간의 합이 m보다 작을 경우

        else if (now_Sum < m)

        {

            right += 1;

            now_Sum += a[right];

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);



    cin >> n >> m;



    for (int i = 0; i < n; i++)

    {

        cin >> a[i];

    }



    solution();



    cout << ans << "\n";



    return 0;

}