[Python] BOJ 백준 21921 블로그

문제

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

풀이

N과 X, 방문자 배열을 입력받아서 연속되는 숫자들의 최대 부분합을 구하는 문제였다.

초기에는 단순하게 index를 sum을 이용해서 구하면서 최대값을 갱신시키는 방향으로 진행했는데, 시간초과가 났다.

import sys

si = sys.stdin.readline

n, x = map(int, si().split())
arr = list(map(int, si().split()))

start, answer, cnt = 0, 0, 1
for i in range(x, len(arr) + 1):
    s = sum(arr[start:i])
    if answer == s:
        cnt += 1
        start += 1
    elif answer < s:
        answer = s
        cnt = 1
    start += 1

if answer != 0:
    print(answer)
    print(cnt)
else:
    print("SAD")

계속해서 합을 구해주는 부분에서 문제가 있다고 판단했다.

이미 한 연산은 반복하지 않기 위해 앞에 들어온 인자를 빼고, 뒤의 인자를 더한 값과 이전 최대 값을 비교해주는 방식으로 전환했다.

다이나믹 프로그래밍을 이용해서 풀었다고 생각했는데, 의도치않게 슬라이딩 윈도우라는 알고리즘을 사용했다. 

슬라이딩 윈도우는 배열에서 일정 범위의 값을 비교할 때 좋은 알고리즘이라고 한다.

아래는 수정한 코드.

import sys

si = sys.stdin.readline

n, x = map(int, si().split())
arr = list(map(int, si().split()))

if max(arr) == 0:
    print("SAD")
else:
    _max = sum(arr[:x])
    answer, cnt = _max, 1
    for i in range(x, n):
        _max = _max + arr[i] - arr[i - x]
        if _max > answer:
            answer = _max
            cnt = 1
        elif _max == answer:
            cnt += 1
    print(answer)
    print(cnt)