[Baekjoon/백준] 2559번: 수열(C/C++)

단계별로 풀어보기 17단계(누적 합) 2번 문제

https://www.acmicpc.net/step/48

누적 합 단계

---

백준 2559번: 수열

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

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일의 온도의 합이 최대가 되는 값을 출력한다.

---

접근 방법

이번 문제는 온도 측정한 날의 수 N과 연속되는 날짜 K를 입력하고 N개의 온도 측정 값을 입력해, 온도 측정 값들 중 연속되는 K개의 값을 더한 합들 중 가장 큰 값을 출력하는 문제다.

우선 예제 2번을 통해서 보자. 예제 2번처럼 입력받았다면 10개의 값을 저장한 배열에 5개씩 비교한다면 0~4, 1~5, 2~6, 3~7, 4~8, 5~9까지의 합을 비교해야할 것이다. 이렇게 보면, 처음 값과 마지막 값을 제외하면 중간 값 이전 값들과 겹친다.

이를 이용해서 문제를 해결하면 된다. 배열의 값들을 처음부터 시작해서 계속 누적해서 더하다가, K개의 값들을 저장하게 되면 최댓값을 비교해서 저장하고 가장 첫값을 뺀다. 그러면 다음 값으로 넘어가게 되면서 처음 값과 마지막 값만 바뀌게 된다.

쉽게 말하면 0번~4번 인덱스까지는 계속 더하기만 하다가, 0번 값을 빼고 5번 값을 더하고, 1번 값을 빼고  6번 값을 더하고 하는 것을 반복하면 된다.

---

코드

#include <iostream>
using namespace std;
#define MAX 100001

int num[MAX];

int findMax(int a, int b) {
	return a > b ? a : b;
}

int main(int argc, char * argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N, K, sum = 0, start = 0, max = -100000001;
	cin >> N >> K;

	for (int i = 0; i < N; i++)
		cin >> num[i];
	
	for (int i = 0; i < N; i++) {
		sum += num[i];

		if (i >= K - 1) {
			max = findMax(max, sum);
			sum -= num[start++];
		}
	}

	cout << max << endl;

	return 0;
}

---

결과

백준 제출 결과

처음에 max값을 생각없이 -101로 했다가 틀렸었다. 이후 간단하게 10만 * -100 + -1을 해서 값을 주었더니 통과했다.