BOJ 1806: 부분합

✔ 문제 링크

BOJ 1806: 부분합

✔ 문제해결전략

• Two Pointer
• 1<=N<=100000이므로 완전탐색(O(N^2)) 불가능

✔ 해결과정

• BOJ: 2230: 수 고르기 와 비슷하다. end가 가리키는 값을 sum에 반영하고 mini 값을 업데이트해야 하는데 end를 업데이트하기 직전에 sum 값에 반영하고 end를 업데이트하여서 처음에 오답이 나왔다. end가 가리키는 값을 먼저 sum에 반영하니 되었다.

✔ 오답 Code

#include <bits/stdc++.h>
using namespace std;

int arr[100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, s, mini = 0x7fffffff;
    cin >> n >> s;
    
    for(int i=0;i<n;i++) {
        cin >> arr[i];
    }

    
    int front = 0, end = 0, sum = 0;
    
    for(int front=0;front<n;front++) {
        while(end<n && sum < s) {
            sum += arr[end];
            end++;
        }
        if(end==n) break;    
        if(sum >= s) {
            mini = min(end-front+1, mini);
        }
        sum -= arr[front];
    }
    
    if(mini==0x7fffffff) cout << 0;
    else cout << mini;
}

✔ 정답 Code

#include <bits/stdc++.h>
using namespace std;

int arr[100001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, s, mini = 0x7fffffff;
    cin >> n >> s;
    
    for(int i=0;i<n;i++) {
        cin >> arr[i];
    }

    
    int front = 0, end = 0, sum = arr[0];
    
    for(int front=0;front<n;front++) {
        while(end<n && sum<s) {
            end++;
            sum += arr[end];
        }
        if(end==n) break;    
        if(sum >= s) {
            mini = min(end-front+1, mini);
        }
        sum -= arr[front];
    }
    
    if(mini==0x7fffffff) cout << 0;
    else cout << mini;
}

✔ Check Point

기존에 풀어본 two pointer 문제들과 다르게 이 문제는 정렬을 하지 않고 바로 진행한다. 그래서 binary search로는 풀이가 불가능하다.

✔ 참고문서

바킹독의 실전알고리즘 - 다이나믹 프로그래밍

바킹독님 감사합니다