[ 21921 ] [ Two-Pointer] 블로그

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

21921번: 블로그

---

풀이과정

---

1. 맨 왼쪽부터 X개의 합계를 먼저 구해두고 시작.

2. [i ~ i+X]의 합계중 최댓값을 구하면 되는 문제

   • 매번 합계를 구해주면 시간이 너무 오래 걸린다.
   • 따라서, [i ~ i+X]의 합계를 구한 다음, 다음 구간의 합계에서는 [i]를 빼주고, [i+X+1]을 더해주면 그게 [i+1 ~ i+X+1]의 합계이다.
   • 이러한 방식으로 진행하면서 합계중 최댓값을 저장해두고, 최댓값이 같은 경우 최댓값의 개수도 같이 증가

3. 최댓값과 최댓값의 갯수를 출력해 준다.

---

소스 코드

---

import sys

input = lambda : sys.stdin.readline().rstrip()
N, X = map(int, input().split())
log = list(map(int, input().split()))

max_visitor = 0
max_visitor_cnt = 0

visitor = sum(log[:X])
left = 0
right = X-1

while right < N:
    if max_visitor < visitor:
        max_visitor = visitor
        max_visitor_cnt = 1
    elif max_visitor == visitor:
        max_visitor_cnt += 1

    if right == N-1:
        break

    visitor -= log[left]
    left += 1
    right += 1
    visitor += log[right]

if max_visitor == 0:
    print("SAD")
else:
    print(max_visitor)
    print(max_visitor_cnt)