본문 바로가기

algorithm/Two Pointer

[C++] BOJ 2559 수열

문제

백준 2559번 수열

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

 

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기

www.acmicpc.net

코드

#include<iostream>
using namespace std;

int n, k, temp[100001], num, sum;

int main() {
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> num;
		temp[i] = num+temp[i-1];
	}

	int ans = -987654321;
	for (int i = k; i <= n; i++) {
		sum = temp[i] - temp[i - k];
		if (ans < sum) ans = sum;
	}
	
	cout << ans;
}

풀이방법

i번째까지 온도의 누적합을 배열 temp에 저장해두고, 이를 이용해 k개씩 합을 구해 그 중 최댓값을 출력한다.

고민과정

누적합을 이용하지 않고 그냥 for문을 돌리면서 더하고 빼는 과정을 구현하려고 했으나, 실패했다..

'algorithm > Two Pointer' 카테고리의 다른 글

[C++] BOJ 2003 수들의 합 2  (0) 2021.05.14
[C++] BOJ 11728 배열 합치기  (0) 2021.05.14
[C++] BOJ 10025 The Lazy Cow  (0) 2021.05.14