파이썬) 블로그 - BOJ

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

21921번: 블로그

 

 

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

arr = list(map(int, input().split()))

left = 0
right = x

max_sum = sum(arr[left:right])

left += 1
right += 1

prev_range = max_sum

cnt = 1

while right <= n:
    this_range = prev_range - arr[left-1]
    this_range += arr[right-1]

    if this_range > max_sum:
        cnt = 1
        max_sum = this_range
    elif this_range == max_sum:
        cnt += 1

    prev_range = this_range
    left += 1
    right += 1


if max_sum == 0:
    print('SAD')
else:
    print(max_sum)
    print(cnt)

이번 문제는 웬지 누적합 문제로 느껴졌지만 누적합 알고리즘을 잘 몰라서 구현으로 풀어냈다.

우선 모든 구간마다 sum()을 사용하면 분명 시간초과가 나올 것이 분명했다.

때문에 다음과 같은 방식으로 풀어냈다.

문제 입력이 만약

5 2
1 4 2 5 1

으로 주어진다고 생각해보자.

초기 값은 arr[0],arr[1]를 합한 5이다.

여기서 옆으로 한칸 옮겨야(arr[1],arr[2]) 다음 범위의 합을 구할 수가 있다.

하지만 여기서 sum을 사용하면 안된다. 그럼 어떻게 해야할까.

이전(arr[0],arr[1])의 합은 5이다. 여기서 옆으로 한 칸 옮긴다는 것은 지금 범위(arr[0],arr[1])에서 맨 왼쪽값 (arr[0])를 빼고 맨 오른쪽 값(arr[1 + 1])을 더한다는 것과 같은 것이다.

즉,

1

4

2

5

1

 

다음과 같은 범위에서 

1

4

초기 값은 위와 같다. 합은 5이다.

여기서 한 칸 옆으로 옮긴다는 뜻은

4

2

위 범위의 합을 구해야 하는 것인데, 생각해보면 

이전 합(5)에서 범위에서 벗어나는 1을 빼고 거기에 범위에 새로 추가되는 값 2를 더한 것과 같다는 말이다.

생각해보면 이런 방식이 누적합이 아닐까하는 생각이 들었다.