[백준] 2559 with C++

문제설명

---

입출력 예제

---

개념

　특정 구간까지의 수열의 합을 구하는 문제다. 단순히 반복문을 중첩시켜 결괏값을 얻으려 하면 십중팔구 시간초과에 걸린다. 이러한 문제처럼 연속된 값을 더하는 문제를 풀 땐 구간합 개념을 이용하면 쉽게 해결할 수 있다.

 

구간합(Prefix Sum)

- 수열에서 특정 구간의 합 

---

풀이

#include <iostream>
using namespace std;

int N, K, temp, sum[100001], ret = -2147483647;

int main() 
{
	cin >> N >> K;

　온도를 측정한 전체 날짜의 수 N, 합을 구하기 위한 연속적인 날짜의 수 K, 구간합을 구할 배열 sum, 구간합 배열의 최솟값 변수 ret을 초기화한다. 이때 ret의 값은 int의 최솟값이다.

 

	for (int i = 1; i <= N; i++)
	{
		cin >> temp;
		sum[i] = sum[i - 1] + temp; // 구간합 배열
	}
	
	for (int i = K; i <= N; i++)
	{
		ret = max(ret, (sum[i] - sum[i - K]));
	}

	cout << ret;

　매일 측정한 온도 temp를 초기화해 주고, 값을 더할 때마다 구간합 배열 sum을 초기화시켜 준다. 그리고 결괏값 ret을 다시 초기화해 주면 된다. 이 과정을 시각적으로 확인해 보면 다음과 같다.

 

 

총합본

#include <iostream>
using namespace std;

int N, K, temp, sum[100001], ret = -2147483647;

int main() 
{
	cin >> N >> K;

	for (int i = 1; i <= N; i++)
	{
		cin >> temp;
		sum[i] = sum[i - 1] + temp; // 구간합 배열
	}
	
	for (int i = K; i <= N; i++)
	{
		ret = max(ret, (sum[i] - sum[i - K]));
	}

	cout << ret;
}