[알고리즘/문제] 백준 2559번: 수열 (C++)

https://www.acmicpc.net/problem/2559

2559번: 수열

#include <iostream>

using namespace std;

int n, k, temp, psum[100001], ret = -10000004;

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> temp;
		psum[i] = psum[i - 1] + temp;;
	}
	for (int i = k; i <= n; i++) {
		ret = max(ret, psum[i] - psum[i - k]);
	}
	cout << ret << "\n";
	return 0;
}

 

이번 문제는 누적합을 활용해 최대값을 구하는 문제였다.

누적합을 적용시키는 기초문제라고 볼 수 있다.

그런데 누적합을 처음쓰는거라 정답코드를 조금씩 보면서 작성을 했다.

 

문제에서 최대값을 구하라고 하면 최소값으로 부터 최대값을 구하고,

반대로 최소값을 구하라고 하면 최대값으로 부터 최소값을 구한다.

예를 들어 최대값을 구해야한다면 다음과같이

ret = max(ret, value);

작은 값들로 부터 ret을 계속 갱신해나가며 최대값을 구한다.

최소값은 min을 쓰면 된다.

ret = min(ret, value);

 

그렇다면 최소값을 어떻게 설정해야할까?

문제의 최악을 가정해본다.

위 문제의 경우에는 -100도가 (10만-1)번 들어오면 제일 낮은 값이 나온다. 그래서 어림잡아 -1000만 정도를 최소값으로 설정한다. 끝점에서 약간의 버퍼같은 역할로 수를 넉넉하게 주는 것이 좋다.

 

[누적합 개념]

https://music-tech.tistory.com/28

[알고리즘/C++] 누적합과 구간합 쿼리

 

[인프런 강의]

https://inf.run/QKBXL

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 강의 - 인프런