[BOJ] 2559. 수열

Jimeaning·2023년 5월 18일

누적합 슬라이딩윈도우

코딩테스트

목록 보기

99/143

Python3

문제

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

키워드

누적합
두 포인터
슬라이딩 윈도우

문제 풀이

문제 요구사항

측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다.
연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램
온도는 모두 -100 이상 100 이하의 정수

변수 및 함수 설명

n : 온도를 측정한 전체 날짜의 수 (2 이상 100,000 이하)
k : 합을 구하기 위한 연속적인 날짜의 수 (1과 N 사이의 정수)
numbers : 측정한 온도 리스트

temp : 누적합
ans : 누적합 중 가장 큰 값

풀이

슬라이딩 윈도우

(출처 : https://learning-e.tistory.com/36)

윈도우(특정 범위)가 있을 때 윈도우 내부 요소 값을 이용해서 문제를 풀이하는 알고리즘.

예를 들면 numbers가 [1, 3, 2, 6, -1, 4, 1, 8, 2] 일 때,
첫 번째로 1 + 3 + 2 + 6 - 1     을 계산하고
두 번째로 	3 + 2 + 6 - 1 + 4 를 계산하면 되는데
중복되는 부분이 생긴다.

=> 이를 코드로 구현하면 처음 계산된 합에서 제일 처음 인덱스를 빼고 마지막 인덱스를 더해주면 된다.

(입력 및 선언)

n개의 날짜와 k를 입력 받는다
n개 만큼의 온도를 입력받는다

numbers 처음부터 k개(인덱스는 0~k-1)까지의 합을 temp에 넣는다.
temp 값을 ans에 넣는다. (이후 누적합이 더 큰 것을 넣으며 갱신할 것이다.)

(슬라이딩 윈도우 구현)

처음 계산된 합에서 제일 처음 인덱스를 빼고 마지막 인덱스를 더해야 한다.
반복문은 k부터 n 전까지 돈다.
제일 처음 인덱스(numbers[i-k])에서 마지막 인덱스(numbers[i])를 뺀 값을 현재까지 계산된 합인 temp에 누적한다.
현재 ans값과 새로 계산된 temp 중 더 큰 값을 ans에 넣어 갱신한다.

(최종 출력)

누적합이 가장 큰 ans 출력

최종 코드

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

temp = sum(numbers[:k])
ans = temp

for i in range(k, n) :
    temp += numbers[i] - numbers[i-k]
    ans = max(ans, temp)

print(ans)

+ 24/02/17 추가 풀이

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

ans = []

for i in range(n - k + 1):
    if ans:
        ans.append(ans[i-1] - temp[i-1] + temp[i + k - 1])
    else:
        ans.append(sum(temp[:k]))

print(max(ans))