[BF] 2003번 수들의 합2

2003번 수들의 합 2

 

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

 

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

 

출력

첫째 줄에 경우의 수를 출력한다.

 

예제 입력

4 2
1 1 1 1

10 5
1 2 3 4 2 5 3 1 1 2

 

예제 출력

3

3

 

해결방법

연속된 수열에 대한 합을 찾는 문제이다

따라서 Left & Right 탐색을 이용할 수 있다

 

일부 경우만 해보기

: 모든 경우 다해보기와 다르게 절대 정답이 될 수 없는 경우는 제외함

 

브루트포스(BruteForce)의 경우에는 시간복잡도를 먼저 구한 다음, 모든 경우를 다해도 시간초과가 나지 않겠다는 판단하에 전체 경우를 탐색하는 것이다.

반면 일부 경우만 탐색하는 것은 정답이 될 수 없는 경우는 탐색을 진행하지 않는다.

 

본 문제는 모든 경우를 수행한다면,

i 번째 수를 구함 → O(N)

각각의 i 번째 수에 대해서 j 번째 수를 구함 → O(N)

∴ O(N²)

O(N²)의 시간복잡도를 가지기 때문에 ⏱시간초과가 발생하게 된다.

따라서 O(N)으로 시간복잡도를 줄여야한다!!

 

 

연속된 수열의 합이 m 인 경우를 찾아야 하므로, 수열의 첫번째 원소부터 탐색을 수행한다

먼저 변수 left 와 right 를 선언한다 (이는 인덱스를 가리키는 변수)

• sum < m : right 인덱스를 한칸 늘려주고, sum에 값을 추가한다
• sum = m : right 인덱스를 한칸 늘려준 뒤, sum에 값을 추가한 뒤, ans 를 증가시킨다
• sum > m : sum에서 값을 빼고, left 인덱스를 한칸 늘려준다

 

 

➕ 코드 수정

예외의 테스트 케이스가 있어 코드를 수정해야 했다

만약 3 8 1 1 에서 m = 5 라고 가정해보자

• L=3, R=3 일 때 R 은 한칸 증가하게 된다
• L=3, R=8 일 때 L 은 한칸 증가하게 된다
• L=8, R=8 일 때 L 은 한칸 증가하게 된다

 

이런 상황에서는 L 이 R 보다 커지게 되어 제대로된 연산이 수행되지 못한다

따라서 R 을 L의 위치로 옮긴 후 sum 값을 다시 set 시켜줘야 한다

 

 

[변경 전]

while(L<n && R<n){
    if(sum < m){
        sum += arr[++R];
    }else if(sum == m){
        sum += arr[++R];
        ans++;
    }else if(sum > m){
        sum -= arr[L++];
    }
}

 

[변경 후]

while(L<n && R<n){
    if(sum < m){
        sum += arr[++R];
    }else if(sum == m){
        sum += arr[++R];
        ans++;
    }else if(sum > m){
        sum -= arr[L++];
        
        if(L>R){
            R = L;
            sum = arr[L];
        }
    }
}

 

 

소스코드

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 10001
#define INF 987654321
using namespace std;

int n,m;
int L,R,sum,ans;
int arr[MAX];

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    
    L = 0;
    R = 0;
    sum = arr[L];
    while(L<n && R<n){
        if(sum < m){
            sum += arr[++R];
        }else if(sum == m){
            sum += arr[++R];
            ans++;
        }else if(sum > m){
            sum -= arr[L++];
            
            if(L > R){
                R = L;
                sum = arr[L];
            }
        }
    }
    
    cout << ans << "\n";
}