백준 1806 (부분합) / 투 포인터 알고리즘

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

완전탐색으로는 시간초과가 나는 문제이다.

🐇 remember

• 투포인터 알고리즘: 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 이용해 원하는 것을 얻는 형태
• 처음에 고민한 예외처리를 똑바로 한 것이 맞는 지 틀리면 다시 돌아가서 봐보자(똑바로 처리가 안된 경우가 있을 수 있당 이번 경우처럼🙄)

❗ 풀이법

투포인터 알고리즘을 알고 있다면 간단하게 풀 수 있는 문제이다.
우선 start와 fin이라는 두 변수를 설정해서 1차원배열을 돈다. 배열에 있는 값을 보는데 이 배열에 있는 값이 원하는 값보다 작다면 fin이라는 포인터(정확하게 포인터는 아니지만)를 다음 배열을 가리키도록 움직인다. 그 다음 fin부터 start까지 있는 배열들을 합을 다시 보고 원하는 값보다 작은 지 큰 지 비교를 한다. 이때 만약 크거나 같다면 start를 하나 증가시킨다. 이제 start이전의 값을 볼 필요가 없기 때문이다.(연속된 수의 합을 구한다고 문제에 명시되어 있다) 이런 식으로 계속 이동하다 보면 연속된 수의 합을 원하는 값과 비교하여 답을 구할 수 있다.
참고로, 마지막 배열이 최소한의 답이 될 수 있기 때문에 fin이 < N가 아닌 <= N로 설정되어야 start부터 fin까지 1 차이나서 답이 될 수 있다. 같은 위치에 있으면 전체 합은 0이다.

✔코드

#include <bits/stdc++.h>
using namespace std;
int N, M, start, fin, sum, flag;
int mn = 100000;
int arr[100001];

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

    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    
    while (start <= fin && fin <= N)
    {
        if (sum >= M)
        {
            flag++;
            mn = min(mn, fin - start);
            sum -= arr[start++];
        }
        else
            sum += arr[fin++];
    }

    if (flag)
        cout << mn;
    else
        cout << 0;
    return (0);
}