[백준_2559] 수열

문제 보기: https://www.acmicpc.net/problem/2559

2559번: 수열

문제

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

 

풀이 과정

코드2의 방식으로 배열을 순회하면서 합을 구하고 순서대로 비교하면서 가장 큰 수를 찾을 수 있는 방식을 구현하였지만 시간 초과가 나오게 되었다. 

이런 이유로 코드1번의 방식으로 해결하였다.

1. 전체적인 콘셉트는 비슷하지만 result라는 배열에 모든 경우의 수를 다 구해 놓고 마지막에 max 함수를 사용하여 가장 큰 값 하나를 선택하는 점이 다르게 구성하였다.

2. for문을 순회하면서 i 번째로 시작하는 수열의 값을 result에 저장하는 방식으로 구성

 

코드

코드 1

import sys

N, M = map(int, sys.stdin.readline().split())
t = list(map(int, sys.stdin.readline().split()))


result = []
result.append(sum(t[:M]))

for i in range(N - M):
    result.append(result[i] - t[i] + t[M + i])

print(max(result))

 

코드 2

import sys

N, M = map(int, sys.stdin.readline().rstrip().split())
t = list(map(int, sys.stdin.readline().rstrip().split()))


def max_func(N, M, t):
    max_num = sum(t[:M])
    for i in range(1, N - M):
        temp = sum(t[i:i + M])
        if max_num < temp:
            max_num = temp

    print(max_num)


max_func(N, M, t)