BOJ 21921. 블로그

블로그 바로가기

슬라이딩 윈도우를 활용한 문제

처음엔 투포인터로 접근하였는데 계속 틀리고,,,
인덱스 접근이 잘못됬는지,, 90퍼 대에서도 틀림,
아무래도 내가 문제였던듯

암튼 틀린이유 찾는 김에 슬라이딩 윈도우 개념도 익히고
슬라이딩 윈도우 활용하여 성공 !

1. 슬라이딩 윈도우란 ?

N 개의 원소를 갖는 배열이 존재하고,
W 개의 창문을 가짐

1. 창문을 왼쪽부터 시작하여 한 칸씩 오른쪽으로 이동
2. 매 순간 창문 안에서의 정보 유출 필요 (ex. 합)

2. 관련 문제 및 응용 방법

🔔 Sliding Window의 기본 아이디어

Window를 한 칸 옮기면 (W-1) 칸은 겹친다 ! 즉, 중복된 항목이 W-1 이므로 이전의 결과를 최대한 응용!

import sys
N, X = map(int, sys.stdin.readline().rstrip().split(' '))
visit = list(map(int, input().split(' ')))
if max(visit) == 0:
    print("SAD")
else:
    max_visit = sum(visit[0:X])
    value = max_visit
    count = 1
    for i in range(X, N):
        value -= visit[i-X]
        value += visit[i]
        if value > max_visit:
            max_visit = value
            count = 1
        elif value == max_visit:
            count += 1
    print(max_visit)
    print(count)