백준 10350

은행

시간 제한 : 5 초 메모리 제한 : 256 MB

문제

월 스트리트에는 0보다 크고 10,000보다 작은 자연수 n개의 은행이 있습니다. 각 은행은 왼쪽(L)과 오른쪽(R) 이웃이라는 정확히 두 개의 이웃을 가지고 있습니다. 첫 번째 은행의 왼쪽 이웃은 마지막 은행이며, 마지막 은행의 오른쪽 이웃은 첫 번째 은행입니다. 각 은행 i(1 ≤ i ≤ n)는 -32,000보다 크고 32,000보다 작은 자본 kᵢ를 가지고 있습니다. 모든 은행의 자본의 합은 양수입니다. 은행의 자본 kᵢ가 음수인 경우, 은행 요정은 마법의 움직임을 통해 자본을 양수로 변경할 수 있습니다. 예를 들어 kᵢ = -7이면 마법의 움직임 후 kᵢ = 7이 됩니다. 그러나 마법의 움직임은 은행 i의 이웃 은행들에게도 영향을 미칩니다. 각 은행은 은행 i의 자본의 절대값만큼 자본이 감소하는 것을 확인합니다. 예를 들어, 은행 L의 자본 kL = 5이고 은행 R의 자본 kR = 11인 경우, 마법의 움직임 후 kL = -2이고 kR = 4가 됩니다.모든 은행의 자본을 0보다 크거나 같게 만들기 위해 Bank Fairy가 수행해야 하는 최소 마법의 움직임 횟수는 얼마인가요?

입력

첫 번째 입력 라인에는 은행의 개수 n이 주어집니다. 두 번째 입력 라인에는 월 스트리트에서 원더랜드로부터 찾을 수 있는 모든 은행의 자본 ki(n>i≥0)이 순서대로 주어집니다. 각 자본은 다음 자본과 공백으로 구분되어 있으며, 마지막 자본은 새 줄 문자로 바로 뒤따릅니다.

출력

출력은 최소한의 마법 이동 횟수의 값이 포함된 단일한 줄로 이루어져 있습니다.

해설

이 문제 같은 경우 최소 이동횟수를 구하는 문제이다. 시간은 대략 5초가 주어져 O(N^2)으로 해결이 가능한 문제이다. 그냥 간단하게 먼저 답을 구하는 목적으로 그리디를 이용해 과정을 도출해낸다 예제입력에서 주어지는 4 1 -2 -1 3을 입력받으면 (-1 2 -3 3), (-1 -1 3 0), (1 -2 3 -1), (-1 2 1 -1), (1 1 1 -2),(-1 1 -1 2), (1 0 -1 1), (1 -1 1 0), (0 1 0 0) 이렇게 총 9번을 움직여야한다 하지만 그리디로 양수가 나올때까지 반복하면 만약 큰수가 주어지면 매우 긴 시간이 필요하기때문에 다 효율적으로 작성해야한다 문제를 보면 모든 은행의 자본의 합은 양수인것을 보아 양수가 아니면 문제를 해결 할 수 없다는 것으로 모든 은행의 합은 1이상이다. 해결 과정을 보면 1 -2 -1 3의 합은 1이다 그리고 푸는과정에서 합은 변하지 않는다 그말은 어떤 규칙성이 있다는 것을 알게되었다 계속 규칙성을 찾던중 음수 구간합의 합이 최소이동 횟수와 똑같다는 즉 입력된 수의 음수가나오는 구간합의 합이 최소 이동횟수라는 것을 알게 되었다. 하지만 반례로 (1 -2 -1 4)같은 경우 음수의 구간합의 합이 9지만 실제로는 6번만 이동한다는것에서 구간합에 어느 값을 대입시켜야한다 여기서 막혀서 질문방에 있던 질문중에 반올림이라는 키워드를 알게되어 전체값은 변하지 않는다는거에 대입해 ((|음수 구간합| / 전체합)반올림)을 진행하면 답을 구할 수 있다는 것을 알게 되었다. 반례 1 -2 -1 4인경우 음수의 구간합이 -1, -2, -2, -3, -1이렇게 나온다 모두 전체합을 나누어 반올림을 하게되면 1 1 1 2 1이 나와 모든합이 6이되어 최소이동 값과 같아 진게된다. 이걸 코드로 구한하면된다.

import math

n = int(input())
banks = list(map(int, input().split()))
prefix = [0]
for i in range(n*2):
    prefix.append(prefix[-1]+banks[i%n])

count = 0

for i in range(n-1):
    for k in range(1, n + 1):
        if prefix[k+i]<prefix[k-1]:
            count += math.ceil(abs(prefix[k+i]-prefix[k-1]) / prefix[n])

print(count)