백준 2559 수열

2011 정보올림피아드 초등부 1번문제이다.

문제풀이

 수열의 연속된 요소들의 합 중 가장 큰 값을 찾는 문제로, 수열을 t라 하면 sum(t[i:i+k])의 최댓값을 구하면 된다.

 1. sum(t[0:k])를 먼저 구한다.

 2. for 문을 k부터 n까지 가며, for 문의 변수가 i라 하면 1의 값에서 t[i]를 더하고 t[i-k]를 빼준다. 이렇게 하면 sum(t[i+k])가 된다.

 3. 2의 값과 1의 값을 비교해 가며 가장 큰 값을 가지고 있다가 for문이 끝나면 반환해준다.

 

시간 복잡도는 수열의 길이만큼의 for문 한번으로 끝나므로, 수열의 길이를 N이라 하면 O(N)이 된다.

주의해야 할 예제로는 n == k인 경우와, 정답이 음수인 경우 정도이다(처음에 ans를 0으로 초기화했다가 틀렸다).

Python Code

import sys
def solve(n,k,t):
    temp = sum(t[:k])
    ans = temp
    for i in range(k,n):
        temp += t[i]
        temp -= t[i-k]
        if temp > ans:
            ans = temp
    return ans if n != k else temp
if __name__ == "__main__":
    n, k = map(int,sys.stdin.readline().split())
    t = list(map(int,sys.stdin.readline().split()))
    print(solve(n,k,t))

문제 링크

2559번: 수열