๋ฌธ์
https://www.acmicpc.net/problem/2559
2559๋ฒ: ์์ด
์ฒซ์งธ ์ค์๋ ๋ ๊ฐ์ ์ ์ N๊ณผ K๊ฐ ํ ๊ฐ์ ๊ณต๋ฐฑ์ ์ฌ์ด์ ๋๊ณ ์์๋๋ก ์ฃผ์ด์ง๋ค. ์ฒซ ๋ฒ์งธ ์ ์ N์ ์จ๋๋ฅผ ์ธก์ ํ ์ ์ฒด ๋ ์ง์ ์์ด๋ค. N์ 2 ์ด์ 100,000 ์ดํ์ด๋ค. ๋ ๋ฒ์งธ ์ ์ K๋ ํฉ์ ๊ตฌํ๊ธฐ
www.acmicpc.net
๋งค์ผ ์ธก์ ํ ์จ๋๊ฐ ์ ์์ ์์ด๋ก ์ฃผ์ด์ก์ ๋, ์ฐ์์ ์ธ ๋ฉฐ์น ๋์์ ์จ๋์ ํฉ์ด ๊ฐ์ฅ ํฐ ๊ฐ์ ๊ณ์ฐํ๋ ํ๋ก๊ทธ๋จ
์กฐ๊ฑด
N์ 2 ์ด์ 100,000 ์ดํ
์ฃผ์ด์ง๋ ์๋ค์ ๋ชจ๋ -100 ์ด์ 100 ์ดํ
์์ ๋ฌธ์ /๋ต
10 2
3 -2 -4 -9 0 3 7 13 8 -3
10๊ฐ์ ์๊ฐ ์ฃผ์ด์ง๊ณ , 2์ผ์น๋ฅผ ์ฐ์์ ์ผ๋ก ๋ํ์ ๋ ๊ฐ ๊ฐ,
=> ์ ๋ต์ 21
ํด๊ฒฐ๋ฐฉ๋ฒ
์ฒจ์ ๊ท์น ์ฐพ์์ ํ๋ ค๊ณ ํ๋๋ฐ, ์ธ๋ฑ์ค๋ฅผ ์๋ชป ๊ณ์ฐํ๋์ง ์ด์ํ ๊ฐ์ด ๋์๋ค. ๊ฐ์ ๋ต์ ๊ฐ์ด๋ ๋์ ํฉ ๊ฐ๋ ์ ๋ฆฌ ์์๋ณด๊ณ ํ์๋ค.
์ฝ๋
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int totalDay, continueDay, max = INT_MIN;
cin >> totalDay >> continueDay;
vector<int> temperates(totalDay + 1, 0);
vector<int> psum(totalDay + 1, 0);
for (int i = 1; i <= totalDay; i++) {
cin >> temperates[i];
temperates[i] += temperates[i - 1]; //prefix sum
}
for (int i = continueDay; i <= totalDay; i++) {
int sum = temperates[i] - temperates[i - continueDay];
if (sum > max) max = sum;
}
cout << max << "\n";
return 0;
}
๋๋ฒ์งธ for ๋ฌธ์์ i ์์์ด continueDay ์ด๋ค. ๊ธฐ์ตํ์.
๋์ ํฉ ์ฐธ๊ณ ์๋ฃ
[10์ฃผ ์์ฑ C++ ์ฝ๋ฉํ ์คํธ] ๋์ ํฉ, Prefix Sum
* ๋์ ํฉ: ์ด๋ค ๋ฐฐ์ด์ ์ ์์๋ถํฐ ๋์ ๋ ํฉ์ ์ ์ฅํ ๋ฐฐ์ด. ์์์๋ถํฐ ๋ํ๋ prefix sum๊ณผ ๋ค์์ ๋ถํฐ ๋ํ๋ suffix sum ์ด ์๋ค. ๋ฐฐ์ด์ ๊ฐ์ด ๋ณํ์ง ์๋ ์ ์ ๋ณ์์๋ง ์ฌ์ฉํ ์ ์๋ค. * ๋์
i-believe-in-me.tistory.com