[Java+Python]2559번, 수열

목차

 

누적 합

 

[Java+Python]11659번, 구간 합 구하기 4

[Java+Python]16139번, 인간-컴퓨터 상호작용

[Java+Python]10986번, 나머지 합

[Java+Python]11660번, 구간 합 구하기 5

[Java+Python]25682번, 체스판 다시 칠하기 2

 

문제

 

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

 

풀이

 

누적 합 문제를 살짝 응용한 문제이다.

 

이전에 풀었던 11659번이 주어진 수열의 특정 누적 합을 구하는 문제였다면,

 

[Java+Python]11659번, 구간 합 구하기 4

[Java+Python]11659번, 구간 합 구하기 4

이번 문제는 주어진 배열에서 특정 길이의 누적합 중 가장 큰 값을 찾는 문제라고 할 수 있다.

 

누적 합을 따로 저장할 배열을 선언한 뒤 최댓값을 구해도 괜찮지만,

 

동적계획법에서 많이 사용했던 방식대로 그때그때 최댓값을 갱신하는 방법을 택했다.

 

풀이 로직은 아래와 같다.

 

1. n, k, 그리고 배열(리스트) arr(lst)을 입력받는다.
2. sum을 선언하고 초기화한 뒤 연속된 처음 k개의 누적 합을 저장한다.
3. max를 선언하고 sum으로 초기화한다. 이 변수를 누적 합 중 최댓값을 갱신하는데 사용한다.
4. 반복문을 돌며 가능한 모든 누적 합을 구하는 동시에 max에 최댓값을 갱신해준다.
5. 출력한다.

누적합 자체에 대한 이해만 있다면 전혀 어려운 문제가 아니었다.

 

계속해서 구현을 보자.

 

Java

 

자바 구현이다. 반복문을 가능하면 적게 사용하려 했지만 이 이상 줄일 방도가 없었다.

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

public class Prob2559_2 {
	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[] arr = new int[n];

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		int sum = 0;
		for (int i = 0; i < k; i++) {
			sum += arr[i];
		}

		int max = sum;
		for (int i = k; i < n; i++) {
			sum += arr[i] - arr[i - k];
			max = Math.max(max, sum);
		}

		System.out.println(max);
	}
}

 

Python

 

파이썬 코드이다. 첫 번째 반복문을 간결하게 줄여주었다.

 

파이썬의 경우 내장함수와 겹치지 않게 변수 이름을 짓는 것도 쉬운 일은 아닌 것 같다.

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
lst = list(map(int, sys.stdin.readline().rstrip().split()))

total_sum = sum(lst[:k])

max_sum = total_sum
for i in range(k, n):
    total_sum += lst[i] - lst[i - k]
    max_sum = max(max_sum, total_sum)

print(max_sum)

 

Performance

 

메모리와 실행 시간은 아래와 같았다.