1 번째 시도

  • 먼저 누적합 sum을 구하고, N(input 개수)만큼 순회하면서 input[i-1]를 sum에서 빼 나가면 매번 i에서 j까지의 누적합을 구할 수 있다. 그리고, i에서 N까지의 범위에서 binary search를 통해 목표(T)에 도달하는 최소 길이를 구하면 된다. 하지만, input 값을 빼는 연산이 $O(N^2)$가 소요되기 때문에 시간초과가 발생할 것이다. 따라서, 모든 sum에서 input 값을 빼지 말고, subSum을 이용하여 binary search에서 비교할 때에만 빼도록 하면 총 연산을 $O(NlogN)$으로 만들 수 있다.
  • sum[i] : i번째 input까지 더한 누적합 (sum[0] : 0)
    • 누적합을 구할 때에는 0 idx를 비워두는 게 계산이나 코드를 작성할 때 편하다 (단, sum[0]을 0으로 초기화해야 한다.)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45



#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

#define MAX_N 100010

int N, T;
int sum[MAX_N];
int res = 1e9;

void bsearch(int left, int right, int subSum) {
	int start = left;

	while (left <= right) {
		int mid = (left + right) / 2;

		if (sum[mid] - subSum >= T) {
			right = mid - 1;
			res = min(res, mid - start + 1);
		} 
		else
			left = mid + 1;
	}
}

void solution() {
	for (int i = 1; i <= N; i++)
		bsearch(i, N, sum[i-1]);
}

int main() {
	scanf("%d%d", &N, &T);
	for (int i = 1; i <= N; i++) {
		int input;
		scanf("%d", &input);
		sum[i] = sum[i-1] + input;
	}

	solution();
	
	printf("%d\n", res == 1e9? 0 : res);
}