문제

매일 아침 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 이하이다.

입력 예시

10 2
3 -2 -4 -9 0 3 7 13 8 -3

출력

첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.

출력 예시

21

문제 풀이

역대급으로 시간이 제일 걸린 문제였던 것 같다.
계속 시간초과가 나서 어떻게 해야 시간초과없이 진행될지 고민했던 것 같다.

일단 관련해서 푸는 힌트는 "누적합"이다.

시간초과가 난 소스코드를 먼저 공개해보자면 이렇다.
시간이 생각보다 오래걸리기는 하더라 아마도 이는 for 문이 이중이여서 그런걸로 생각되긴한다.

n,k = map(int, input().split(" "))
temperatureArray = list(map(int,input().split()))

def temperature(temperatureArray, k):
    arr = []
    div = 0
    for num in range(0,len(temperatureArray)):
        if num+k < len(temperatureArray)+1:
            for num2 in range(num, num+k):
                div = div + temperatureArray[num2]
            arr.append(div)
            div = 0 # 초기화

    return arr

arr = temperature(temperatureArray,k)
print(max(arr))

중간에 누적합이라는 걸 알아서 누적합을 적용하니 시간은 줄긴했는데,
그래도 여전히 시간초과가 발생하는 것을 확인했다.
3815초까지는 줄였다..

n, k = map(int, input().split(" "))
temperatureArray = list(map(int, input().split()))


# def prefix_sum(temp, n):
#     result = 0
#     for i in range(n):
#         result += temp[i]
#     return result


def temp_prefix_sum(temp, n, k):
    memo = {}
    arr = []
    for i in range(0, n+1):
        memo[i] = sum(temp[0:i])
    for i in range(0,n):
        if i+k <= n:
            arr.append(memo[i+k]-memo[i])
    return arr


temp_array_result = temp_prefix_sum(temperatureArray, n, k)
print(max(temp_array_result))

해당 문제를 풀다보니, 이 알고리즘을 써보라고 해서 써봤는데
그냥 이 문제 자체가 해당 알고리즘에 적합한? 문제인 것 같더라.
시간초과는 문제 해결, 새로운 알고리즘을 선사해주신 분께도 감사..

알고리즘을 간단하게 설명드리면 "슬라이딩 윈도우 기법" 이라는 알고리즘으로,
아래 글 참고해보면 좋을 것 같다.

https://blog.fakecoding.com/archives/algorithm-slidingwindow

n, k = map(int, input().split(" "))
temperatureArray = list(map(int, input().split()))

def max_num(temp,k):
    max_sum = float('-inf')
    start_index = 0
    curr_sum = 0

    for end, val in enumerate(temp):
        curr_sum += val
        if end - start_index +1 == k:
            max_sum = max(max_sum,curr_sum)
            curr_sum -= temp[start_index]
            start_index += 1
    return max_sum

print(max_num(temperatureArray,k))