[1806] - 부분합

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

1806번: 부분합

연속된 수의 부분합이라 정렬을 쓰지 못해서 누적합으로 풀었다.

 

문제 풀이

• 먼저 입력받은 수열을 인덱스를 하나 늘려 누적합 해주기.
• 최대 - 최소를 해주면 그 부분의 값이 나오니 최대/최소 인덱스 생성
• 반복문을 돌면서 값이 S(n[1])보다 크면 가능하니 can을 true로 설정, 길이 비교해서 작으면 바꿔주기.
• max가 n[0]+1이 되는 경우가 있어 제한 걸어주고, temp값 갱신
• 답 출력

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Baekjoon.Gold
{
    class _1806
    {
        static void Main(string[] args)
        {
            int[] n = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            int[] sum = new int[n[0] + 1];
            //누적합
            for(int i = 1; i <= n[0]; i++)
                sum[i] = arr[i - 1] + sum[i-1];

            int min = 0; //왼쪽
            int max = 1; //오른쪽

            int temp = sum[1];
            int ans = n[0];
            bool can = false; //가능한지 아닌지
            while(max - min > 0 && max <= n[0])
            {
                //합이 더 크면 가능하고, 길이 조절
                if (temp >= n[1])
                {
                    if (ans > max - min)
                        ans = max - min;
                    min++;
                    can = true;
                }
                else
                    max++;

                if (max > n[0]) //인덱스 넘어갈수 있어서
                    temp = sum[max - 1] - sum[min];
                else
                    temp = sum[max] - sum[min];
            }

            if (can)
                Console.WriteLine(ans);
            else
                Console.WriteLine(0);
        }
    }
}