백준 2559 - 수열 (Python3)

코드

# 2559 수열
import sys
input = sys.stdin.readline

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

# 맨 처음 부분 수열의 합
_sum = sum(arr[:k])

# 비교를 위한 임시 변수 생성
tmp = _sum

# k부터 n-1까지 k의 길이를 가지는 부분 수열의 합을 구함
for i in range(k, n):
    
    # arr[i]번째 값이 들어오고
    # arr[i-k]번쨰 값이 빠짐
    # ex) k가 2인 경우
    #    => 처음 arr[0:2] => arr[0] + arr[1] (tmp)
    #    => 다음 구간 => arr[1:3] => arr[1] + arr[2]
    # 위 구간의 변화를 tmp로 표현하면 arr[0]가 사라지고 arr[2]가 새로 추가됨
    # 따라서 아래의 식이 도출됨
    tmp += arr[i] - arr[i-k]
    _sum = max(tmp, _sum)
    
print(_sum)

문제 해설

투 포인터 알고리즘을 이용하는 문제.

처음에 너무 쉽게 문제를 풀었더니 역시나 시간 초과로 실패했다. 따라서 투 포인터 알고리즘을 이용하여 문제를 다시 풀었고 정답으로 인정됐다.

자세한 설명은 주석으로 대신합니다!!