📘 문제

문제링크 : https://www.acmicpc.net/problem/1806 (단계별로 풀어보기 : 투 포인터)

📝 문제 풀이

처음 문제이해를 부분합 중에 그 합이 S가 되는 것으로 생각하여 계속 삽질을 했다. ❗️문제는 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것 이다. 문제의 핵심은 두 개의 포인터를 가지고 같은 시작점에서 시작하여 부분합을 계산하며 진행하는 것이다. 다음과 같이 알고리즘을 생각했다. ptr1을 왼쪽 포인터 ptr2를 오른쪽 포인터라 하자. 나는 ptr1=0 ptr2=1로 시작하여 배열의 첫 번째 수로 이루어진 구간합에서 시작하여 sum이 S보다 작으면 숫자를 더해주어야함으로 ptr2를 늘려 숫자를 한개 더해주고, sum이 S보다 같거나 크면 다음 과정은 숫자를 줄여야함으로 ptr1을 증가시키는 과정을 반복하였다. ptr2가 더이상 증가할 수 없을 때 까지 반복하면서 최소구간길이를 갱신해주면 최솟값을 구할 수 있다. 아마 최악의 시간복잡도로 하여도 O(2n)으로 O(n)의 시간복잡도가 예상된다.

while(1)

1. 만약 구간합 >= S 이면 구간합 길이 최소이면 최신화. ptr1 증가.
2. 만약 구간합 < S 이면 ptr2 증가. ptr2가 N보다 같거나 커져서 배열의 범위를 벗어난 곳을 탐색하게 될 시 break

• 1,2번 ptr증가 시 구간합 최신화 필요.

또 하나 주의할 점은 ❗️해당 조건을 만족하는 구간이 없으면 0을 출력해야 한다.

✏️ 알고리즘 스케치

빨간색이 옳은 알고리즘스케치다.

💻 소스코드

#include <iostream>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

void input(int *N, int *S, int **arr);
void solution(int N, int S, int *arr);

int main()
{
    fastio;
    int N, S;
    int *arr;
    input(&N, &S, &arr);
    solution(N, S, arr);
    return 0;
}

void input(int *N, int *S, int **arr)
{
    cin >> *N >> *S;
    *arr = new int[*N];
    for (int i = 0; i < *N; i++)
        cin >> (*arr)[i];
}

void solution(int N, int S, int *arr)
{
    int ptr1 = 0, ptr2 = 1;
    int sum = arr[ptr1];
    int minlength = N + 1;
    while (1)
    {
        if (sum >= S)
        {
            if (minlength > ptr2 - ptr1)
                minlength = ptr2 - ptr1;
            sum -= arr[ptr1];
            ptr1++;
        }
        else
        {
            if (ptr2 == N)
                break;
            sum += arr[ptr2];
            ptr2++;
        }
    }
    if (minlength != N + 1)
        cout << minlength;
    else
        cout << 0;
}

코드는 웬만하면 포인터를 써서 작성하려고 노력하는 중이다. 사실 포인터가 익숙하지 않다면 입력되는 값들을 전역변수로 선언하여도 알고리즘 문제를 풀때는 무방하다.