[백준] 2003번: 수들의 합 2

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

문제

알고리즘 접근 방법

1. 단순 반복문 = O(N^2) 방식
i=1~N 까지 돌면서 반복문으로
i+1 ~ N까지 더해보면서 M이 되면 break

2. 2-pointer = O(N) 방식
start, end를 각각 정해서
start ~ end 까지의 합이
M보다 작으면 end 를 하나씩 늘려가고
M보다 크면 start를 하나씩 늘려간다.
같으면 result++

N이 10만이었으면 어떻게 풀었을까 생각해보기

풀이

1. 단순 반복문 = O(N^2) 방식

#include <iostream>

// 수들의 합 2
using namespace std;

int A[10001];

int main(){

    int N, M, result = 0;

    cin >> N >> M;

    for(int i=0; i<N; i++)
        cin >> A[i];

    for(int i=0; i<N; i++){
        int sum = 0;
        for(int j=i; j<N; j++){
            sum += A[j];
            if (sum == M){
                result++;
                break;
            }
        }
    }

    cout << result;

    return 0;
}

2-pointer = O(N) 방식

#include <iostream>

// 수들의 합 2 - 2 포인터
using namespace std;

int A[10001];

int main(){

    int N, M, result = 0;

    cin >> N >> M;

    for(int i=0; i<N; i++)
        cin >> A[i];
    
    int start = 0, end = 0;
    int sum = A[start];
    for(start; start<N; start++){
        while(sum < M && end < N){
            end++; sum += A[end];
        }
        
        if (sum == M) { result++; } 
        
        sum -= A[start]; 
    }

    cout << result;
    return 0;
}

정리

우와아 신기

시간차이 ㄷㄷ