[BaekJoon / C++] 1806번 : 부분합

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

1806번: 부분합

---

문제

 

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

 

---

입력

 

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

 

---

출력

 

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

---

풀이

 

#include <iostream>
 
using namespace std;
 
int arr[100001]{};
 
int main()
{
    int n, m, i;
    int L = 0, H = 0;
    int result = 100001;
 
    cin >> n >> m;
 
    for (i = 0; i < n; i++)
        cin >> arr[i];
 
    int sum = arr[0];
 
    while (L <= H && H < n)
    {
        if (sum < m)
        {
            sum += arr[++H];
        }
        else if (sum == m)
        {
            result = (result < H - L + 1 ? result : H - L + 1);
            sum += arr[++H];
        }
        else if(sum>m)
        {
            result = (result < H - L + 1 ? result : H - L + 1);
            sum -= arr[L++];
        }
    }
 
    if (result == 100001)
        cout << 0 << "\n";
    else
        cout << result << "\n";
 
    return 0;
}

 

이 문제는 투포인터 알고리즘을 사용하면 간단하게 해결할 수 있었다.

 

이 문제에서 사용된 투포인터 알고리즘은

L과 R 두 가지 포인터 인덱스를 사용하며 기본적으로 R 포인터를 통해 배열을 탐색해가며 sum을 구하고

만약 sum이 목표값과 같다면 result 변수를 통해 현재의 길이와 이전에 저장된 최소 길이를 비교하여 더 낮은 길이를 result에 저장하고, R 포인터를 우측으로 옮긴다.

만약 sum이 목표값 이상이라면 위와 같이 길이 비교를 통해 길이를 저장하고, L 포인터를 우측으로 옮기면서 탐색을 진행하는 방식이다.

 

마지막으로 만약 result값에 변동이 없다면 목표값을 뛰어넘는 부분합이 없다는 뜻이므로 0을 출력하고, 그렇지 않다면 result 값을 출력한다.