Algorithm/구현

[백준] 2559번 수열

HANNI하니 2023. 10. 23. 18:30

사용 언어 - Python3

문제 -  2559번 수열

 

2559번: 수열

첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기

www.acmicpc.net

 

정답

누적된 숫자들의 합 기억하기 (정답 맞춘 여부 X)

컴퓨터에게 기억하는 방법 알려주기

1. prefix라는 누적합 배열 생성

2. B만큼 떨어져 있는 누적합끼리 빼주기

3. 최대값 구하기

A,B = map(int,input().split())
arr = list(map(int,input().split()))

# 누적합 배열 만들기
prefix = [0 for _ in range(A+1)] # 0 으로 채워진 list 만들기
for i in range(A):
    prefix[i+1] = prefix[i] + arr[i]

# 간격B만큼 prefix 차이를 구하기
answer = []
for k in range(B,A+1):
    answer.append(prefix[k] - prefix[k-B])

print(max(answer))

 

 

레퍼런스

  • 정답 깃허브

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/2559_%EC%88%98%EC%97%B4.py