백준 21921: 블로그 (Python)

 

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

21921번: 블로그

 

투 포인터 이용

n, x = map(int, input().split())
visitors = list(map(int, input().split()))

i = j = 0
temp = result = 0
cnt = 0

for i in range(n):
    # 끝 포인터 이동
    while j-i < x and j < n:
        temp += visitors[j]
        j += 1

    # x일
    if j-i == x:
        if result < temp:
            result = temp
            cnt = 1
        elif result == temp:
            cnt += 1

    # 시작 포인터 값 빼주기
    temp -= visitors[i]

if result == 0:
    print("SAD")
else:
    print(result)
    print(cnt)

 

다 풀고 다른 사람의 코드를 참고해보다가

슬라이딩 윈도우 알고리즘을 적용해보았다.

 

슬라이딩 윈도우란?

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다.

 

n, x = map(int, input().split())
visitors = list(map(int, input().split()))

# 초기값
result = temp = sum(visitors[:x])
cnt = 1

for i in range(x, n):
    temp += visitors[i] - visitors[i-x] # 누적합 계산

    if result < temp:
        result = temp
        cnt = 1
    elif result == temp:
        cnt += 1

if result == 0:
    print("SAD")
else:
    print(result)
    print(cnt)

 

 

투 포인터 이용했을 때

슬라이딩 윈도우 이용했을 때