1806 partial sum

์•Œ๊ณ ๋ฆฌ์ฆ˜ (๋ธŒ๋ฃจํŠธํฌ์Šค)

1. ๊ธธ์ด๋ฅผ 1๋ถ€ํ„ฐ N๊นŒ์ง€ ๊ฒ€์‚ฌ
2. ํ•œ ๊ธธ์ด๋ฅผ ๊ฒ€์‚ฌํ•  ๋•Œ ๋‹ค์Œ์„ ์‹คํ–‰
	1. ์ˆ˜์—ด์˜ ์ฒ˜์Œ๋ถ€ํ„ฐ ๊ธธ์ด๋งŒํผ ๋”ํ•˜๊ณ  sum์— ์ €์žฅ, ์ฒซ๋ฒˆ์งธ๋ฅผ ๋”ฐ๋กœ first์— ์ €์žฅ. -> S๋ฅผ ๋„˜๋Š”์ง€ ํ™•์ธํ•˜๊ณ  ์•ˆ๋„˜์œผ๋ฉด 2 ์‹คํ–‰
	2. ์ˆ˜์—ด์˜ (๊ธธ์ด)๋ฒˆ์งธ๋ถ€ํ„ฐ ๊ฒ€์‚ฌ. ์œ„์—์„œ ๊ตฌํ•œ sum์—์„œ first๋ฅผ ๋นผ๊ณ , ํ˜„์žฌ์˜ ์ˆ˜์—ด์›์†Œ๋ฅผ ์ง‘์–ด๋„ฃ์Œ. -> ๊ฒ€์‚ฌ -> ์•„๋‹ˆ๋ฉด first์— ๋‘๋ฒˆ์งธ ์ €์žฅ
3. ๋‹ค ํ–ˆ๋Š”๋ฐ๋„ ์•ˆ๋˜๋ฉด 0 ๋ฐ˜ํ™˜
-> ํ†ต๊ณผ๋Š” ๋˜์ง€๋งŒ, ์•„์ฃผ ๋А๋ฆผ

์•Œ๊ณ ๋ฆฌ์ฆ˜(๋‘ ํฌ์ธํ„ฐ)

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์™€ ๊ฐ™์•„์ง€๋ฉด ๊ธธ์ด๋ฅผ ์ €์žฅํ•˜๊ณ  ๋์„ ํ•˜๋‚˜ ๋” ๋Š˜๋ฆฌ๊ณ , ์ปค์ง€๋ฉด ๊ธธ์ด๋ฅผ ์ €์žฅํ•˜๊ณ  ์ฒ˜์Œ์„ ํ•˜๋‚˜ ์ค„์ด๋Š” ์‹์œผ๋กœ ๊ณ„์† ๋ฐ˜๋ณต.
-> ํ›จ์”ฌ ๋น ๋ฅด๋‹ค.

์ฝ”๋“œ

#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;
}