[C++] BOJ 1806번: 부분 합

학교에서 진행하는 수업에서 공유받은 알고리즘 문제를 풀어보았다.

 

문제의 난이도는 골드 4로, 투 포인터를 활용해 푸는 것을 권장받은 문제이다.

문제 링크

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

문제 분석

 이번 문제는 입력으로 길이 N짜리 수열이 주어진다. 해당 수열에서 연속된 수들의 부분 수열의 합에서 그 합이 S 이상이 되는 것 중 가장 짧은 부분 수열의 길이를 구하는 프로그램을 작성해야 한다.

 

 시작점과 끝점이 있을 때, 시작점부터 끝점까지의 부분 수열의 합은 끝점이 시작점에서 멀어질 수록 점점 커지는 경향이 있다. 만약 수열에 음수가 포함된다면 이러한 성질을 갖지 못하지만, 해당 문제에서는 '10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다'고 조건에 나와있으므로 성립한다.

 

 시작점부터 끝점까지의 부분 수열의 합은 끝점이 시작점에서 멀어질 수록 점점 커지고, 부분 수열의 합에서 그 합이 S 이상이 되는 것 중 가장 짧은 부분 수열의 길이를 구하는 문제이므로 투 포인터 알고리즘이 문제 풀이에 적합하다.

자료 구조 및 알고리즘

 투 포인터에 대한 설명 및 예제 문제 풀이는 [C++] BOJ 3273번: 두 수의 합에서 다루었다.

문제 풀이

 이번 문제에서 투 포인터를 사용할 때에는 이전에 풀었던 [C++] BOJ 3273번: 두 수의 합과 달리 start와 end가 모두 같은 곳인 배열의 시작점을 가리키도록 하여 문제를 해결하였다.

전체 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[100001];
int N;
int S;
int minLength = 200000; // 200000은 100000보다 큰 임의의 수

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> S;

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

    int start = 0;
    int end = 0;
    int arrSum = 0;

    while (start <= end)
    {
        if (arrSum >= S)
        {
            minLength = min(end - start, minLength);
            arrSum -= arr[start++];
        }
        else if (end < N)
        {
            arrSum += arr[end++];
        }
        else
        {
            arrSum -= arr[start++];
        }
    }

    if (minLength == 200000)
        cout << 0 << '\n';
    else
        cout << minLength << '\n';

    return 0;
}