알고리즘 :: 백준 :: 2559 - 수열

 

 

 

 

 

 

 

❔문제

🔗문제링크

 

🔄 문제 및 입출력 조건 파악

• 입력: 요소 개수 ≤ 100,000 (-100 ≤ 각 요소 ≤ 100)
• 출력: 연속 K일 합의 최댓값

✏️ 문제풀이

최대 10만개의 입력이, 각 입력은 -100까지 가능하므로 초깃값은 -10,000,001로 잡는 것이 좋습니다.

언제나 문제의 범위 바깥에 초깃값을 두도록 합시다.

• 최댓값을 구해야하면 문제의 범위 바깥에 있는 최솟값으로 시작하고,
• 최솟값을 구해야하면 문제의 범위 바깥에 있는 최댓값으로 시작하는게 중요합니다.

1. 누적합을 이용한 풀이

 

'K'가 주어지기 때문에, 먼저 K일 까지의 합이 초깃값이 됩니다.

1. 2일-(K+1)일은 1일-K+1일 합에서 1일-1일 합을 뺀 것과 같다.
2. 3일-(K+2)일은 1일-K+2일 합에서 1일-2일 합을 뺀 것과 같다.
3. 4일-(K+3)일은 1일-K+3일 합에서 1일-3일 합을 뺀 것과 같다.

2. 누적합을 이용하지 않은 풀이

K일 까지의 합을 먼저 구합니다.

• 현재 합에서 (K+1)일 값을 더하고, 1일차 값을 뺀것이 더 큰지 비교합니다
• 현재 합에서 (K+2)일 값을 더하고, 2일차 찺을 뺀것이 더 큰지 비교합니다
• 현재 합에서 (K+3)일 값을 더하고, 3일차 값을 뺀것이 더 큰지 비교합니다

두 방법 모두 결국에는 같은 이야기이므로 좀 더 빨리 떠오른 쪽으로 구현하면 됩니다.
이때 요소는 최대 10만, 각 요소는 -100이 될 수도 있고, 최댓값을 구하는 문제이므로 초깃값은 -10,000,001로 잡는다. (초깃값은 정답 범위 바깥으로)

📝 코드

1. 누적합을 이용

#include <bits/stdc++.h>
using namespace std;

int N, K;
array<int, 100'001> arr;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	cin >> N >> K;
	for (int i = 1, temp; i <= N; ++i) {
		cin >> temp;
		arr[i] = arr[i - 1] + temp;
	}
		
	int result = -10'000'001;	// -100 * 100,000
	
	for (int i = K; i <= N; ++i)
		result = max(result, arr[i] - arr[i - K]);
	
	cout << result << '\n';
}

 

🔗 코드 링크

2. 누적합을 이용하지 않음

#include <bits/stdc++.h>
using namespace std;

int N, K, sum, result;
array<int, 100'001> arr;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> N >> K;
	for (int i = 0; i < K; ++i) {
		cin >> arr[i];
		sum += arr[i];
	}
	result = sum;    // sum of (0~K-1) is initial value.
	for (int i = K; i < N; ++i) {
		cin >> arr[i];
		sum += (arr[i] - arr[i - K]);
		if (result < sum) result = sum;
	}
	cout << result;
}

 

🔗 코드 링크

🕧 결과