1806 partial sum
알고리즘 (브루트포스)
1
2
3
4
5
6
1. 길이를 1부터 N까지 검사
2. 한 길이를 검사할 때 다음을 실행
1. 수열의 처음부터 길이만큼 더하고 sum에 저장, 첫번째를 따로 first에 저장. -> S를 넘는지 확인하고 안넘으면 2 실행
2. 수열의 (길이)번째부터 검사. 위에서 구한 sum에서 first를 빼고, 현재의 수열원소를 집어넣음. -> 검사 -> 아니면 first에 두번째 저장
3. 다 했는데도 안되면 0 반환
-> 통과는 되지만, 아주 느림
알고리즘(두 포인터)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1. length에 최대 길이를 저장, first = 0, last = 1, sum = num[0] 를 저장.
2. first <= last 이고 last <= N일때 반복
1. sum이 S보다 작을 때
sum += num[last++]
2. sum이 S와 같을 때
length = min(length, last-first)
sum += num[last++]
3. sum이 S보다 클 떄
length = min(length, last - first)
sum -= num[first++]
3. 쉽게 얘기해서 검사할 길이의 처음과 끝을 표현하는 두 변수를 선언하고,
끝을 하나씩 늘려가면서 sum을 구하되, sum이 S와 같아지면 길이를 저장하고 끝을 하나 더 늘리고, 커지면 길이를 저장하고 처음을 하나 줄이는 식으로 계속 반복.
-> 훨씬 빠르다.
코드
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
#include <iostream>
#define MAX_N 100000
using namespace std;
int num[MAX_N];
int sumNum[MAX_N];
int N, S;
int shortestSequence(int start);
int main() {
cin >> N >> S;
for (int i = 0; i < N; i++)
cin >> num[i];
int start = S / 10000;
cout << shortestSequence(start);
}
int shortestSequence(int start) {
sumNum[0] = num[0];
for (int i = 1; i < N; i++) {
sumNum[i] = sumNum[i - 1] + num[i];
}
for (int i = start; i <= N; i++) {
int first = num[0];
int sum = sumNum[i - 1];
if (sum >= S)
return i;
for (int j = i; j < N; j++) {
sum -= first;
sum += num[j];
if (sum >= S)
return i;
first = num[j - i + 1];
}
}
return 0;
}