[백준] 2003. 수들의 합

[문제]

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

[풀이]

 

N,M이 주어지고 길이가 N인 배열에서 구간합이 M인 경우의 수를 찾아서 출력하는 문제

구간합 문제길래 이중 for문을 사용해서 풀려고 했다.

하지만 시간 제한이 0.5초인데 M의 범위가 1부터 3억이라서 이중 for문을 사용하면 시간초과가 발생한다.

 

따라서 구간합 구하는 알고리즘인 투 포인터 알고리즘을 사용해서 풀었다.

start , end 를 배열의 첫번째 index부터 시작해서

현재 구간 합이  M보다 작으면 end를 +1, M보다 크면 start를 +1 

이런 방식으로 start, end 의 index를 조절하면서 구간 합을 구했다.

 

 

 

[코드]

 

시간 : 0ms

 

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

int N,M;
int arr[MAX];


int main(void)
{
    int total=0;

    scanf("%d %d",&N,&M);
    for(int i=0;i<N;i++)    scanf("%d",&arr[i]);
    
    int start =0 ;
    int end =0;
    int sum =arr[0];
    
    
    while(start <= end && end < N)
    {
        if(sum < M) sum += arr[++end];
        else if( sum > M)
        {
            sum -= arr[start++];
            if( start > end && start <N){
                end=  start;
                sum= arr[start];
            }
        }
        else if (sum == M)
        {
            total++;
            sum += arr[++end];
        }
    }
    
    printf("%d",total);
    return 0;
    
}