[BaekJoon] 백준 알고리즘 2559번 / 수열 / 투포인터 / Python

문제 

 

접근방법

해당 문제는 연속적인 부분합 중에서 가장 큰 값을 찾는 문제이다. 가장 간단하게 시간복잡도 O(N^2)의 알고리즘으로 구할 수 있다.

그 방법은 완전 탐색 방법으로, 각 구간을 시작하는 인덱스 i와 끝나는 인덱스 j에 대해, i부터 j까지의 합을 구해서 가장 큰 값을 찾는 것이다. 이를 위해서는 2중 반복문을 사용하여 모든 구간에 대해 합을 구해야 한다.

하지만 해당 문제의 N은 100_000 이하로 주어지며, 시간복잡도 O(N^2)이므로 시간초과로 이어질 수 있다.( 2억개 미만이면 가능)

 

소스 코드

"""
1. 아이디어
- 투포인터 활용
- for문으로, 처음 K개 합산
- 다음 인덱스 더해주고, 이전 인덱스 빼주면서 최대값 갱신

2. 시간복잡도
- 완전 탐색일 경우 O(N^2) -> 10_000_000_000 > 2억개!, 시간초과 발생
- 투포인터로 할 경우 O(N) -> 100_000 < 2억개!, 가능!

3. 자료구조
- 각 숫자들 N개 저장 배열 : int[]
    * 최대 100 이므로, int 가능
- N에서 K개의 값을 저장할 변수 : int
    * 최대 : K * 100 = 100_000 * 100 = 10e7, int 가능
- 최대값 저장 변수 : int
"""

import sys
input = sys.stdin.readline

N,K = map(int, input().split())
nums = list(map(int, input().split()))
sum = 0

# K개 더해주기
for i in range( K ):
    sum += nums[i]
maxv = sum

# 다음 인덱스 더해주고, 이전 인덱스 빼주기
for j in range( K, N ):
    sum += nums[i]
    sum -= nums[i-k]
    maxv = max(maxv, sum)

print( maxv )