[BaekJoon] 2003. 수들의 합

BaekJoon Online judge

[2003] 수들의 합

1.Let’s Think

1. 완전 탐색

   완전탐색에 대해 고민해보자.

    int ans = 0;
    for(int i = 0; i < N; i++) {
    	int temp = 0;
    	for(int j = i; j < N; j++) {
        	temp += arr[j];
            if(temp == M) ans++;
            else if(temp > M) break;
        }
    }
    return ans;
   

   위와 같이 완전 탐색으로 문제에 접근하면 Time Complexity의 경우 O(N^2)이 된다. 이는 배열의 최대 수가 10000임을 고려하면 최소 10^8번의 loop를 고려해야한다. 즉, 10^8번의 loop가 대략 1초라고 가정했을 때, 시간 제한을 넘어선 아이디어가 된다.

2. Two Point

   startPoint와 endPoint를 두어 잘 조절한다면 O(N)의 시간내에 문제를 해결할 수 있을 듯하다.

   int startPoint, endPoint;
   startPoint = endPoint = 0;
   int ans = 0, sum = 0;
   while(startPoint < N) {
   	if(sum < M) {
       	if(endPoint >= N) break;
           sum += arr[endPoint++];
       }
       else {
       	if(sum == M)
       		ans++;
           sum -= arr[startPoint++];
       }
   }
   return ans;
   

   위와 같이 문제에 접근한다면 Time Complexity의 경우 O(N)이 된다. 즉, 제한 시간내에 문제의 결과를 도출할 수 있다.

2.Solve the Problem

#include<stdio.h>
#include<vector>
using namespace std;

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    vector<int> arr(N);
    for(int i =0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    
    int s, e, sum, ans;
    s = e = 0;
    sum = 0;
    ans = 0;
    while(s < N) {
        if(sum < M) {
            if(e >= N) break;
            sum += arr[e++];
        }
        else {
            if(sum == M) {
                ans++;    
            }
            sum -= arr[s++];
        }
    }
    printf("%d", ans);
    return 0;
}

3.End