[Codeground 42번] 부분배열

문제 출처 :

https://www.codeground.org/practice/practiceProblemList

알고리즘 분석 :

문제 해결에 필요한 사항

1. 투 포인터 :: http://www.crocus.co.kr/search/투 포인터

2. Prefix Sum :: http://www.crocus.co.kr/search/prefix

이 문제가 부분 합을 요구하는 문제이니 prefix sum을 이용해야 함을 인지 할 수 있다.

그리고 부분 합에서 부분 배열을 구해야하니 prefix sum과 투 포인터를 조합하면 된다는 것을 알 수 있다.

결국 prefix sum과 투 포인터 두가지 알고리즘으로 해결 할 수 있는 문제이다.

이 두가지를 가지고 문제의 요구에 맞도록 prefix sum을 이용하여 미리 구해둔 부분 합에서 

투 포인터를 이용하여 문제를 해결하여 보자.

PS(Problem Solving)를 말로 기술하는 것 보다 직접 코드를 보고 이해하는 것이 더 쉬울 것 같다.

소스 코드 : 

#include <iostream>
#include <cstdio>
 
#define min(a,b)(a < b ? a : b)
 
using namespace std;
 
int arr[100002];
int sum[100002];
int main()
{
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++)
    {
        int n, s;
        
        scanf("%d %d", &n, &s);
 
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
            if (i == 0)
                sum[i] = arr[i];
            else
                sum[i] = sum[i - 1] + arr[i];
        }
 
        int p1 = 0, p2 = 0;
        int ans = 99999999;
        while (p1 < n)
        {
            if (sum[p2] - sum[p1] >= s)
            {
                ans = min(ans, p2 - p1);
                p1++;
            }
            else if (sum[p2] - sum[p1] < s)
            {
                
                if (p2 + 1 >= n)
                    break;
                p2++;
            }
 
        }
        if (ans == 99999999)
            printf("#testcase%d\n0\n", tc);
        else
            printf("#testcase%d\n%d\n", tc, ans);
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>