240501 [BOJ/백준] 21921. 블로그

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

---

나의 코드

import sys

X, N = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
dp = [0]*(X+1)

for i in range(1, X+1):
    if i <= N:
        dp[i] = dp[i-1] + arr[i-1]
    else:
        dp[i] = dp[i-1] - arr[i-1-N] + arr[i-1]

if max(dp) == 0:
    print('SAD')
else:
    print(max(dp))
    print(dp.count(max(dp)))

 

결과

---

BFS이후로 별로 생각안하고 풀 수 있는 문제였다. 누적합으로 된 건 이제 무엇이든 풀 수 있을 것 같다!ㅎㅎ

 

(+ 알고리즘 분류에 슬라이딩 윈도우가 있어서 찾아보니 else문에 쓴 게 슬라이딩 윈도우 방법이었다. 갯수가 N개를 넘어갈 때부터는 맨 앞의 값을 빼고 뒤의 값을 더하는 방법 => 전체 넓이는 같다.

투포인터, 슬라이딩 윈도우, 누적합의 차이를 알 수 있었다.)