📒 문제
매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때,
3 -2 -4 -9 0 3 7 13 8 -3
모든 연속적인 이틀간의 온도의 합은 아래와 같다.
그림 1. https://www.acmicpc.net/problem/2559
이때, 온도의 합이 가장 큰 값은 21이다.
또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며,
그림 2. https://www.acmicpc.net/problem/2559
이때, 온도의 합이 가장 큰 값은 31이다.
매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오.
입력
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다. K는 1과 N 사이의 정수이다. 둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -100 이상 100 이하이다.
출력
첫째 줄에는 입력되는 온도의 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.
✏️ 풀이
이 문제는 처음에 너무 쉬워서 당황했지만,,,
역시나였다.
그냥 그렇게 쉬웠을 리가 없었던 문제다.
N, K = map(int, input().split())
tem_list = list(map(int, input().split()))
result_list = []
for i in range(len(tem_list)):
if i + K - 1 == len(tem_list) - 1:
result_list.append(sum(tem_list[i:i+K]))
break
result_list.append(sum(tem_list[i:i+K]))
print(max(result_list))이렇게 그냥 반복하면서 최대값을 찾으면 될줄 알았지만,
시간초과가 발생한다.
그 이유는 입력부분에서 N과 K의 최대값이 100,000이 될 수 있기 때문인데, for문을 돌면서 계속 sum을 K값에 얹어서 진행해주기 때문에 제한시간인 1초를 넘어갈 수 있게 되기 때문이다.
그래서 방법을 고민해보다가,
sum을 한번만 쓸 수 있는 방법이 떠올랐다.
처음에 선언해줄때만 sum을 이용하고, for문을 돌면서 부분합을 맨앞값을 빼주고 맨뒷값을 더해주는(?) 식으로 만들어주면, for문을 돌면서도 시간초과가 나지 않도록 할 수 있다.
말이 조금 헷갈리는데, 다음 코드를 통해 알 수 있다.
N, K = map(int, input().split())
tem_list = list(map(int, input().split()))
part_sum = sum(tem_list[:K])
result_list = [part_sum]
for i in range(0, len(tem_list)-K):
part_sum = part_sum - tem_list[i] + tem_list[i+K]
result_list.append(part_sum)
print(max(result_list))또한, 애초에 for문의 범위를 len(tem_list)-K로 해주면서,
불필요한 break문 부분을 지울 수 있다.
이 코드를 통해 메모리는 38188kb, 시간은 120ms로 나름 적당한 결과를 얻을 수 있었다.
