PS/백준 알고리즘[BOJ]

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

BE_개발자 2023. 10. 30. 20:59
728x90
반응형

1. 문제

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

 

2559번: 수열

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

www.acmicpc.net

이미지 예시

구간 K만큼의 합을 구하고 그 중에서 최댓값을 구하는 문제이다.

2. 풀이

구간합

https://wondrous-developer.tistory.com/47

 

동적 계획법을 이용하여 구간합 구하기

1. 구간합의 의미와 시간복잡도 어떤 배열이 주어졌을 때 원하는 구간의 합을 말한다. 2. 구간합 알고리즘 구간합 고등학교때 배운 수열의 합을 이용하여 원하는 구간의 합을 구하는 법을 배웠다

wondrous-developer.tistory.com

 

#include<iostream>

using namespace std;
int N, K;
long long int sum[100000];
long long int tem[100000];



int main(void) {
	long long int max;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		int day;
		cin >> day;
		sum[i] = sum[i - 1] + day;

		if (i >= K) {
			tem[i] = sum[i] - sum[i - K];
			if (i == K) max = tem[i];
			if (tem[i] > max) max = tem[i];
		}
	}
	cout << max;
		

	return 0;
}
728x90
반응형