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