백준 2559, 구간합 문제

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

2559번: 수열

연속되는 배열의 요소를 더한 값의 최대값을 구하는 문제이다. 연속되는 값을 더하는 문제의 경우 구간합(부분합) 알고리즘으로 접근해야 한다!

Key Point

1. 연속되는 수의 합을 구해야 하는 문제이다. -> 구간합(부분합) 알고리즘을 사용한다.
2. 최대값을 구하는 문제이다. -> 최소값을 상수로 결정해야 한다. (해당 최소값과 비교를 통해 최대값을 갱신하기 때문)
   • 만약, 최소값을 구하는 문제일 경우, 최대값을 상수로 결정한다.
   • 즉, 초기값은 답의 범위 밖에서 결정해야 한다.

구간합(부분합)

1. 0번 인덱스는 비우고 시작한다. (인덱스가 1이면 한 개를 저장, 인덱스가 4이면 네 개 요소가 저장된 것이다.)
2. 처음부터 끝까지 한 요소(한 개)씩 누적해서 더한 값을 psum 배열에 저장한다.
3. 필요한 구간에 대한 합을 구하기 위해 구간 (x,y)에 대하여 psum[y] - psum[x-1] 로직을 사용한다.

문제 코드

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

int N,K,temp;
int ret = -10000000;
int psum[100001];

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;

	return 0;
}

• 값의 최소 값이 -100이고, 더해질 수 있는 값의 개수가 10만 - 1 이므로, 최소 값을 -1000만으로 지정하였다.
  • 따라서 계속 구간 합을 구한 것과 비교를 통해 최대값을 갱신하게 된다.

C++ - max/min 함수

• min(a, b) : a와 b 중 더 작은 값을 반환한다.
• max(a,b) : a와 b 중 더 큰 값을 반환한다.

 

잘못 접근한 코드

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

const int maxN = 100001;
int n,k,sum,ret;
int arr[maxN];


int main(){
	
	cin >> n >> k;
	
	for(int i = 0; i < n; i++){
		cin >> arr[i];
	}
	
	for(int i = 0; i+k-1 < n; i++){ // 값이 최대 10만까지 갈 수 있기 때문에 2중 for문은 시간초과하는 알고리즘이다. 
		for(int j = i; j < i+k; j++){ 
			sum += arr[j];
		}
		if(sum > ret) ret = sum;
		sum = 0;
	}
	
	cout << ret;
	
	return 0;
}

해당 문제의 데이터는 최대 10만까지 저장될 수 있다. 따라서 다음과 같은 O(n^2)의 시간복잡도를 갖는 이중 for문을 사용하게 되면 시간초과에 의해 통과되지 못한다. 따라서 이 문제는 구간합을 써야 한다.

 

 

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

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