[알고리즘] 2559번: 수열

0. 문제

 

2559번: 수열

 

문제

매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.

예를 들어, 아래와 같이 10일간의 온도가 주어졌을 때,

3 -2 -4 -9 0 3 7 13 8 -3

모든 연속적인 이틀간의 온도의 합은 아래와 같다.

 

이때, 온도의 합이 가장 큰 값은 21이다.

또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일간의 온도의 합은 아래와 같으며,

이때, 온도의 합이 가장 큰 값은 31이다.

매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

예제 입력 1

10 2
3 -2 -4 -9 0 3 7 13 8 -3

예제 출력 1

21

예제 입력 2

10 5
3 -2 -4 -9 0 3 7 13 8 -3

예제 출력 2

31

 

---

1. 문제 이해

1. 정수 N과 K를 저장한다.
   1. “한개의 공백을 사이에 두고 순서대로 주어진다.” → getline 한 후에 split를 해야 하나? 그냥 cin으로 받아도 되나?
2. N개의 정수를 배열에 저장한다.
3. 이중 for문으로 합을 구하고 가장 큰 합을 변수에 따로 저장해 둔다.
4. 가장 큰 합을 출력한다.

 

---

2. 제출

가. 시간 초과

//백준 2559번: 수열
#include <iostream>

using namespace std;

int N, K, sum, big, a[100004];

int main(){
	cin >> N >> K;
	for(int i=0; i<N; i++){
		cin >> a[i];
	}
	for(int i=0; i+K<N; i++){
		sum = 0;
		for(int j=0; j<K; j++){
			sum += a[i+j];
		}
		if(sum > big) big = sum;
	}
	cout << big << "\\n";
	return 0;
}

이중 for문의 시간 복잡도 O(n2)가 너무 큰 것 같다.

 

또한 값의 합이 음수인 경우가 있기 때문에 big의 초기화 값을 다음과 같이 설정한다.

• N은 2 이상 100,000 이하이다.
• K는 1과 N 사이의 정수이다.
• N개의 정수는 모두 -100 이상 100 이하이다.

 

첫 번째 sum의 최솟값보다 확실하게 작은 값을 구해야 한다.

 

최악을 경우 N=100000, K= 100000 - 1, N=-100이다.

 

근삿값으로 100000 * -100 = -10000000 아래로 설정한다.

 

---

나. 누적합

// 백준: 2559번: 수열
#include <iostream>

using namespace std;

int n, k, temp, psum[100001], big= -10000004;

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++){
		big=max(big, psum[i] - psum[i-k]);
	}
	cout << big << "\\n";
	return 0;
}

누적합을 사용해서 시간 복잡도를 O(n)까지 낮춘다.

 

big을 -10000004로 초기화한다. (-4는 마진)

 

참고로 cout << psum[0] << "\\n"; → 0이다.

 

---