BOJ - 2559 수열

문제 링크

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

시간, 공간 제한

시간 : 1초

공간 : 128Mb

초기 문제 접근 방향

시간 복잡도 생각

- 일단 최대 들어 올수 있는 입력이 10,0000 이고 완전 탐색으로 모든 경우의 수를 구해 비교하는 것은 O(n^2) 이기 때문에 dp 풀이를 시도함

- ans[i] 값을 i번째 input에서 연속된 k일동안 온도의 합이라고 한다면

- ans[i] = ans[i - 1] - input[i - 1] + input[i + (k - 1)] 이라는 점화식을 도출함

- max_element를 사용하여 ans 범위안의 최댓값을 찾아냄

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int n, k;
	cin >> n >> k;
	vector<int> ans;
	vector<int> input;
	input.resize(n + 1);
	ans.resize(n + 1, -100000000);
	for (int i = 1; i <= n; ++i)
	{
		int val;
		cin >> val;
		input[i] = val;
	}
	int sum = 0;
	for (int i = 1; i <= k; ++i)
	{
		sum += input[i];
	}
	ans[1] = sum;
	for (int i = 2; i <= n - (k - 1); ++i)
	{
		ans[i] = ans[i - 1] - input[i - 1] + input[i + (k - 1)];
	}
	cout << *max_element(ans.begin() + 1, ans.begin() + ans.size());
	return (0);
}

문제 접근 다른 방향

- prefix sum 구간합을 사용한 풀이 가능했음

- psum[i] 는 i번째 까지의 구간합으로 정의하여  psum 배열을 구한다.

- 최댓값을 구하기 위해 ret = max(ret, psum[i] - psum[i - k])

- 초기  ret은 문제에서 최소로 나올수 있는 -1000000 으로 설정

for (int i = 1; i <= n; ++i)
{
	cin >> temp;
    psump[i] = psum[i - 1] + temp;
}
   
for (int i = k; i <=n; ++i)
{
	ret = max(ret, psum[i] - psum[i - k]);
}

dp 풀이를 생각해 보기전에 구간합으로 풀 수 있을지 한번 생각해 보자!