[BAEKJOON] 2559 수열

• 알고리즘 분류: 구간합, 누적합, 수학
• 난이도: Silver3
• 문제내용:
  • 전체 날짜 수 N과 연속적인 날짜의 수 K와 전체 날짜를 준다.
  • 연속적인 K일 온도의 합중 가장 큰것을 구해라
• 사이트 : https://www.acmicpc.net/problem/2559

2559번: 수열

문제풀이

 이번 문제는 누적합, 구간합 기본 문제이다. 개념이나 이론적인 설명은 아래에 사이트에 참조 하면된다.

https://jih3508.tistory.com/50

[알고리즘 이론] 구간합, 누적합(prefix sum)

 

이번 문제는 최대 데이터가 100000이고 시간이 1초라서 아래와 같이 작성하면 O(N ^ 2)이 나오기 때문에 시간 초과가 나올것이다.

N, K = map(int, input().split())

array = list(map(int, input().split()))
max_value = -100 * K
for i in range(N - K):
    max_value = max(max_value, sum(array[i: i + K]))

print(max_value)

 시간 초과를 피할라면 O(NlogN)이하의 시간 복잡도가 나오는데 이번 구간합 누적합의 원리를 알면 O(N)의 시간이 걸린다.

1.  누적합을 구한다.
2. 최대 값을 저장한 변수를 선언한다.
3. 다시 전체 index를 탐색하는데 자신의 index와 연속 K일 만큼 차이를 구해서 그중 큰 값을 최대 값으로 저장한다.
4. 최대 값을 출력한다.

Code

Python

N, K = map(int, input().split())

array = list(map(int, input().split()))
s = [0, array[0]]
for i in range(1, N):
    s.append(array[i] + s[i])

max_value = -100 * K
for i in range( N - K + 1):
    max_value = max(max_value, s[i + K] - s[i])

print(max_value)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;


public class Main {

	public static void main(String[] args) throws  IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] array = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			array[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] s = new int[N + 1];
		for(int i = 0; i < N; i++) {
			s[i + 1] = s[i] + array[i];
		}
		
		int max_value = -100 * K;
		for(int i = 0; i <= N - K ; i++) {
			max_value = Math.max(max_value, s[i + K] - s[i]);
		}
		
		System.out.println(max_value);
				
	}
			
}