[Python][백준/BOJ] 21921번 : 블로그

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

21921번: 블로그

 

내 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
viewer = [0] + list(map(int, input().split()))

if max(viewer) == 0:
    print('SAD')
else:
    window = sum(viewer[:m])
    answer = window
    cnt =1
    for i in range(m, n+1):
        window += viewer[i] - viewer[i-m]
        if window > answer:
            answer = window
            cnt =1
        elif window == answer:
            cnt +=1

    print(answer)
    print(cnt)

 

코드 리뷰

슬라이딩 윈도우

슬라이딩 윈도우 문제를 처음 풀어보았다. 지금까지는 단순히 부분합이라고 여기고 풀었던 문제가, 연속된 수를 이용하는 거라면 슬라이딩 윈도우라는 알고리즘에 해당하는 것이었다.

 

viewer = [0] + list(map(int, input().split()))

1부터 n까지 그 자리에 저장하기 위해서 이렇게 초기화했다.

if max(viewer) == 0:
    print('SAD')
else:
    window = sum(viewer[:m])
    answer = window
    cnt =1
    for i in range(m, n+1):
        window += viewer[i] - viewer[i-m]
        if window > answer:
            answer = window
            cnt =1
        elif window == answer:
            cnt +=1

그리고 부분합이 0이라는 것은 결국 숫자 배열의 부분 합도 0, 숫자들도 0이라는 것이므로 먼저 조건을 처리한다.

앞으로는 m 크기의 틀을 가진 윈도우를 이리저리 움직이며 연산을 진행할 것이다.

그리고 window라는 수에 0부터 m까지의 합을 저장한다.

이후 m부터 n까지 윈도우를 움직이면서 연산한다.

i는 1씩 증가하는 상태에서 window에 i번째의 값을 더해주고, 동시에 i-m번째의 수를 뺀다. (한 칸 옆으로 이동한 윈도우)

만약 최댓값을 발견했다면 cnt는 1로 초기화해주고, 최댓값과 동일한 크기라면 +1 을 해준다.

슬라이딩 윈도우의 개념을 익히기에 좋은 문제였다.

 

https://beehand.tistory.com/114

슬라이딩 윈도우 알고리즘 (Sliding Window)

슬라이딩 윈도우에 대한 설명은 여기서 확인할 수 있다.