[백준] 21921 블로그

투포인터
avatar
2024.12.27
·
2 min read

2639

🔗 문제 링크

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

💻 코드

import sys
input = sys.stdin.readline 

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

current = 0
result = 0
cnt = 0

left, right = 0,0

while right < n:
    current += visited[right]

    if right - left + 1 > x:
        current -= visited[left]
        left += 1

    if right - left +1   == x:
        if current > result:
            result = current 
            cnt = 1
        elif current == result:
            cnt += 1
    right += 1

if not result:
    print("SAD")
else:
    print(result)
    print(cnt)

🤷‍♂️ 풀이

  • 투포인터로 접근해서 풀었다.

  • left, right를 설정한 후에 right를 증가시킨다.

    • 구간 길이 > x이면, 더했던 값을 빼주고 left를 증가

    • 구간길이 == x일 경우에는 최댓값을 갱신해주는데 이 때 최댓값이 또 나오는 경우라면 누적으로 구간 개수를 센다.

  • 시간복잡도는 left, right가 배열을 순회하니까 O(n)







- 컬렉션 아티클