[C++] 백준(BOJ) - 2559 : 수열
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
매일 아침 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일의 온도의 합이 최대가 되는 값을 출력한다.
알고리즘
- 투포인터
- 누적합
풀이
- 누적합을 저장할 배열 psum을 미리 선언
- 최대값을 구하기 위해 sum 값을 최소로 초기화 및 선언
- 1번째 index부터 구간합을 누적합 배열에 저장 (0번째 index는 0으로 초기화하기 위함)
- 구하고자하는 연속적인 날짜 수 k를 기준으로 최대값을 갱신해나가는 반복문 돌리기
코드
// BOJ - 2559 : 수열
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int n, k, psum[100004], res = -INF;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> k;
for (int i = 1; i <= n; i++)
{
int tmp;
cin >> tmp;
psum[i] = psum[i - 1] + tmp; // 구간합 1번째 인덱스부터 만들기
}
/*
for (int i = 1; i <= n; i++) cout << psum[i] << ' ';
cout << '\n';
*/
for (int i = k; i <= n; i++)
{
res = max(res, psum[i] - psum[i - k]);
}
cout << res << '\n';
return 0;
}
평가
- ‘연속된’ -> 구간합을 구하는 문제로 연상하기
- 구간합 구하는 공식 암기하기
- 투포인터 알고리즘을 활용하여 시간복잡도를 낮추기
