[파이썬] 백준 2559 : 수열 (실버3)

[파이썬] 백준 2559 : 수열 (실버3)

 

2559번: 수열

---

문제

---

풀이

0. 방향성 생각.

누적된 값을 계속해서 사용한다. 딕셔너리에 현재 날짜까지 합을 구해놓고 구간이 주어지면 두 지점의 누적값을 뺀다.

 

1. 입력, 누적 딕셔너리 만들기.

n,k = map(int,input().split())
temp = list(map(int,input().split()))
table = {}
for i in range(n) :
    if i==0 :
        table[i+1] = temp[i]
    else :
        table[i+1] = table[i]+temp[i]

 

2. 누적 최대값 갱신, 출력

cum_temp = table[k]
for i in range(k+1,n+1):
    if cum_temp < (table[i]-table[i-k]) :
        cum_temp = table[i]-table[i-k]
print(cum_temp)

---

전체코드

n,k = map(int,input().split())
temp = list(map(int,input().split()))
table = {}
for i in range(n) :
    if i==0 :
        table[i+1] = temp[i]
    else :
        table[i+1] = table[i]+temp[i]

cum_temp = table[k]
for i in range(k+1,n+1):
    if cum_temp < (table[i]-table[i-k]) :
        cum_temp = table[i]-table[i-k]
print(cum_temp)

누적합인걸 모르면 시간초과가 날 수 있는데, DP 처럼 이전에 계산된 값을 이용해서 푼다는 점을 이용해서 리스트, 딕셔너리를 만들어두고 풀면 쉽게 풀 수 있다.