BOJ [C#]) 1806번 부분합

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

1806번: 부분합

1. 문제

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

 

2. PS

- 처음에 일일이 다 구해서 값을 찾으려 하여 시간초과가 남..

- front와 end 변수로 index값을 조종해 줌.

- end 좌표를 뒤로 보내면서 sum값이 s값을 넘어갈 때 front값을 땡겨 sum값을 줄여주는 방식.

- 그러면서 end-front의 최솟값을 지속적으로 갱신해줌.

using System;

class Program
{
    static void Main() {
        string[] s1 = Console.ReadLine().Split(' ');
        int n = int.Parse(s1[0]);
        int s = int.Parse(s1[1]);
        
        string[] s2 = Console.ReadLine().Split(' ');
        int[] arr = new int[n];
        int tmp = 0;
        for(int i = 0; i < n; i++) {
            arr[i] = int.Parse(s2[i]);
            tmp += arr[i];
        }
        if(tmp < s) Console.Write(0);
        else {
            int min = n+1, sum = 0;
            int front = -1;
            for(int end = 0 ; end < n; end++) {
                sum += arr[end];
                
                while (sum >= s) {
                    if(min > end-front) min = end-front;
                    sum -= arr[++front];
                }
            }
        Console.WriteLine(min);
        }
    }
}