백준 1806번 부분합

🔒[문제 url]

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

🔑알고리즘

연속된 수의 합과 $S$를 계속 비교해야하므로, Two pointer를 이용해 연속된 수의 합을 갱신해가며 $S$보다 큰 값 중 연속된 길이의 최솟값을 출력한다.

• 연속된 수의 합을 어떻게 갱신하는가?
  • 합은 다음 셋 중 하나의 상태를 가진다.
  1. $S$보다 큰 상태 : 최솟값 갱신 후, 왼쪽 포인터를 옮겨 더 짧아질 수 있는지 확인한다.
  2. $S$와 같은 상태 : 최솟값 갱신 후, 왼쪽 포인터를 옮겨 더 짧아질 수 있는지 확인한다.
  3. $S$보다 작은 상태 : 합이 커져야하므로, 오른쪽 포인터를 옮긴다.
     
     
• 즉, 1 혹은 2 라면 왼쪽 포인터를 , 3이라면 오른쪽 포인터를 옮겨가며 답을 도출한다.

🐾부분 코드

생략한다. 알고리즘을 이해한다면 구현은 쉽다.

🪄전체 코드

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

int n,m;
int numList[100001];

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> numList[i];
}


void SOLVE()
{
    int start = 0,end = 0;
    int sum = numList[0];

    int ans = 2e9;
    while(end < n)
    {
        if(sum >= m)
        {//연속된 수의 합이 S 이상
            if(start == end)
            {// 길이가 1이면 최소이므로 출력 후 종료
                cout << 1;
                exit(0);
            }
            ans = min(ans,end - start + 1);
            sum -= numList[start++];
        }
        else
        {//연속된 수의 합이 S 미만
            sum += numList[++end];
        }
    }

    if(ans != 2e9) cout << ans;
    else cout << 0;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

코딩테스트에서 강한 변별력을 지닌다는 Two Pointer를 처음 접해봤다.
난이도는 매우 낮지만 변별력은 강하다?! 이건 못 참지!
Gold4정도 되면 쉬운 문제는 아닌데, 알고리즘만 알면 웬만한 Silver1보다 쉬워지는 것같다. 해보진 않았지만 이분 탐색으로도 풀 수 있을 것같다.