백준 21886 - Countdown (Python)

문제 정보

• https://www.acmicpc.net/problem/21886
• 수학, 누적 합

---

문제 정리

카운트다운 타이머가 있다. 타이머는 처음에 k초로 설정되며, t초가 지난 경우 시간은 max(k-t, 0)이다. 이 타이머를 시작한 뒤 n번 특정한 시간에 타이머를 확인했고, 그때 보인 숫자들을 모두 더한 값이 s가 되었다. 확인한 시간과 s가 주어질 때, k를 찾아야 한다.

---

풀이

그래프가 k에서 시작해서 감소하다 어느 지점에서 0이 되고 그 뒤로 쭉 0이 된다.
즉, 0이 되는 어느 지점을 x라고 두고, x 이전 시각에 타이머를 확인한 경우 보이는 숫자를 전부 더했을 때 k가 되는지를 체크하면 된다.
식을 정리해보면,

$(k - a_0) + (k - a_1) + ... + (k - a_i) = s$
$ik - (a_0 + a_1 + ... + a_i) = s$
이므로, 누적합 배열을 미리 전처리해주고, i를 한칸씩 옮겨가며 탐색할 경우, 위 식을 만족하는k값을 O(N)으로 구할 수 있다.

---

후기

G4가 맞아보이는듯?

---

코드

# 백준 21866

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


def solve(N, S, arr):
    accSum = [0] * N
    accSum[0] = arr[0]
    for i in range(1, N):
        accSum[i] = accSum[i-1] + arr[i]

    for i in range(1, N+1):
        temp = S + accSum[i-1]
        if temp % i == 0:
            result = temp // i
            if i < N and arr[i] > result:
                return result

    return result


def main():
    N, S = map(int, input().split())
    arr = list(map(int, input().split()))
    print(solve(N, S, arr))


main()