[백준/C++] 알고리즘 1806번 - 부분 합

안녕하세요! 테크지니어22입니다.

오늘은 백준 알고리즘 1806번 - 부분 합 을 풀어보도록 하겠습니다.

 

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

 

 

[문제 접근]

- 제한 시간이 0.5초이고 n이 10만이하이기 때문에 O(N^2)풀이는 불가능합니다.

-  1차원 배열에서 O(N^2)이 아닌 풀이를 원하기 때문에 이분탐색 혹은 투포인터가 떠올랐습니다.  

 

[풀이 전략]

- 투포인터를 이용하여 풀이하였습니다.

 

[코드]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n , s ;
int arr[100'001] ; 

int main() {
  ios::sync_with_stdio(0);
    cin.tie(0); 
    int res = 1'000'000'000; 
    cin >> n >> s ;

    for(int i = 0 ; i < n ; i++) cin >> arr[i]; 
    int tot = arr[0] ; 
    int en = 0 ; 
    for(int st = 0 ; st < n ; st++) {
        while(tot < s && en + 1 < n) { tot += arr[++en] ; }  
        
        if(tot < s) continue;
        res = min(res,en - st+1) ; 
        tot -= arr[st];
    }
    if(res == 1'000'000'000) res = 0 ; 
    cout << res ; 
 
}

 

[배울 점]

- st를 옮길때마다 이전 st가 영향을 주었던 부분을 원래대로, 즉 더했었다면 빼주어야 합니다.

- st를 옮길때마다 부분합을 처음부터 다시 더해진다면 투포인터 풀이가 아닐뿐더러 시간복잡도가 O(N^2)이 되어버립니다.

- 누적합에 대한 이분탐색의 풀이도 가능합니다.