[백준 2003] 알고리즘 106일차 : 수들의 합 2

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

2003번: 수들의 합 2

투포인터 C++ 

대략 25분

 

수열의 부분합 중 M을 만족시키는 경우의 수를 출력하는 문제이다

 

접근방법

투포인터를 사용해서 합이 M보다 작으면 -> end를 오른쪽으로 이동시키고

크면 -> start를 오른쪽으로 이동시킨다.

M과 같으면 경우의 수(cnt)를 1증가시키면서 end를 오른쪽으로 이동시킨다.

 

오답노트

구간의 합이 M보다 큰 경우 중 start와 end가 같은 점을 가리키고 있을때

그대로 start를 오른쪽으로 이동시키면 end보다 커져서 반복문을 나가게 된다.

그래서 1 2 1 과 같은 케이스에서 뒤에 1을 보지 못하고 2에서 반복문이 종료된다.

따라서 합이 M보다 클 때 start와 end가 같은 점을 가리키고 있으면 end를 오른쪽으로 이동시키고

start와 end가 다른 점을 가리키고 있으면 start를 오른쪽으로 이동시키면 된다.

 

이 예외는 수열 중 하나의 숫자가 M보다 클때 발생하는 예외이다.

나는 if문으로 따로 처리해줬는데 더 나은 로직이 있는지 모르겠다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    //input
    int N, target;
    cin >> N >> target;
    
    int arr[N+1];
    for(int i = 0 ; i < N ; i++){
        cin >> arr[i];
    }
    
    //process
    int s,e;
    s = e = 0;
    int sum = arr[0];
    int cnt = 0;
    while(s <= e && e < N){
        if(sum > target){
            if(s == e){
                sum += arr[++e];
            }else{
                sum -= arr[s++];
            }
        }else if(sum < target){
            sum += arr[++e];
        }else{
            cnt++;
            sum += arr[++e];
        }
    }
    
    //output
    cout << cnt << "\n";
    return 0;
}