취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2559번 문제인 수열이다.
문제는 아래 링크를 확인하자.

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

길이 K의 구간합들 중 최솟값을 구하는 문제이다.

가능한 길이 K의 구간들에 대하여 원소들을 직접 더하는 것을 2중 for문등을 이용해 구현한다면 상당한 시간을 소비하게 된다. N이 10만이고 K가 5만인 경우 5만개의 정수의 합을 5만1회 하게 됨을 관찰하자. 이러한 구현의 시간복잡도는 $O(N^2)$이다.

대신, 구간 [1,R]의 합을 R번 인덱스에 저장해둔 prefix sum 배열을 $O(N)$에 구해두면 각 길이 K의 구간합 또한 $O(N)$에 전부 둘러볼 수 있게 된다. 그 값들 중 최댓값을 구해 문제를 해결하자.

위 내용을 구현할 때, 배열의 첫 원소의 인덱스를 0으로 잡으면 0번 원소에 관련된 처리를 할 때 예외처리를 할 필요성이 생길 수 있어 구현이 번거로워진다. 배열의 첫 원소의 인덱스를 0이 아닌 1로 지정하면 그러한 예외처리 없이 구현을 간단하게 할 수 있다. 자세한 구현은 아래의 소스코드를 참고하자.

한편, 큐(queue) 자료구조나 투 포인터 구현을 이용한 슬라이딩 윈도우(sliding window) 접근으로도 문제를 해결할 수 있을 것이다.

배열에 음수가 저장되어있을 수 있음에 유의해 구현하자. 즉, 문제의 답이 음수가 될 수도 있으므로, 구현에 따라 최댓값을 저장할 변수의 초깃값을 0으로 해두면 문제를 틀릴 수도 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N, K;
int psum[100001];
int mx = -1000000007;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> K;
	
	for (int i = 1; i <= N; i++) {
		cin >> psum[i];
		psum[i] += psum[i - 1];
	}

	for (int i = K; i <= N; i++) mx = max(mx, psum[i] - psum[i - K]);

	cout << mx;
}