[파이썬] 백준 2559 수열

https://www.acmicpc.net/problem/2559

2559번: 수열

처음에 풀때 제한시간 안보고 뭐야 왜이리 쉬워 했는데

시간초과떠서 당황한문제

 

2중 for문으로 풀면 안되고 for문을 한번만 돌게 해야하는 문제였다.

 

일단 2중 for문으로 푸는 방법은 아래와 같다.

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

MAX = -21e8
for i in range(N-K):
    temp_add = 0
    for j in range(K):
        temp_add += arr[i+j]
    if temp_add >MAX:
        MAX = temp_add

print(MAX)

 

이를 단축하려면

일단 k일 만큼 합해진 온도를 구한 후,

for문을 한번 돌면서 맨 앞 index값은 합한 온도에서 빼주고

맨 뒤 인덱스 값은 추가해주면 된다.

 

즉,

K=3이라고 가정했을때,

0~2인덱스 더한 값을 temp_k로 두고,

temp_k-arr[0]+arr[3]을 하고 MAX값이랑 비교하면 된다.

그러면 temp는 1~3 인덱스를 더한 값이 된다.

 

전체 코드)

N, K = map(int, input().split())
arr = list(map(int, input().split()))
temp_k = sum(arr[:K])
MAX = temp_k
for i in range(N-K):
    temp_k-=arr[i]
    temp_k+=arr[i+K]
    if temp_k > MAX:
        MAX = temp_k

print(MAX)