[백준][python]2559 수열

문제

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

소스코드1

if __name__ == "__main__":
    n, k = map(int,input().split())
    arr = list(map(int,input().split()))


    sum_val = sum(arr[0:k])
    res = sum_val
    rm = 0
    include = k


    while include < n :
        tmp_val = sum_val - arr[rm] + arr[include]
        res = max(res,tmp_val)
        sum_val = tmp_val
        rm += 1
        include +=1

    print(res)

소스코드2

if __name__ == "__main__":
    n, k = map(int,input().split())
    arr = list(map(int,input().split()))
    res = [sum(arr[:k])]

    for i in range(n-k):
        res.append(res[i] - arr[i] + arr[k+i])
    print(max(res))

설명

입력값 N이 100,000이기 때문에 for문을 돌면서 k개씩 또 for문을 돌거나 sum을 해서 더해주면 시간초과가 날것으로 예상했다.

 

0번부터 K-1번 원소까지 더해주고 (K개) 0번째 원소를 빼고 K-1번째 원소를 하나씩 늘려가면서 더해주면 1번의 반복문으로 문제를 해결할 수 있겠다고 생각했다.

 

소스코드1은 냅다 구현해보았고 소스코드2는 조금 더 가독성있게 바꿔보았다. 소스코드2는 결과값을 모두 배열에 넣고 max함수를 이용해서 최대값을 구했는데도 시간이 20ms 줄었다. 소스코드1은 매번 max 함수를 써서 시간이 조금 더 걸렸다.