IT_Study/Python
[백준 10350] : Banks
__Vivacé__
2024. 9. 17. 00:51
애드 혹 문제를 찾다가 알게 됐다
문제 분석
수학, 누적합, 애드혹
# 문제 조건
양 끝 부분이 서로 연결된 리스트 활용
- list 길이 = N
- idx = 0은 idx = N-1에 연결
- idx = N-1은 idx = 0에 연결
- list는 k라는 요소를 가지고 있음
- -32,000 <= k <= 32,000
# Magic Move
- 특정 요소에 magic move 적용 시, k => -k가 된다
- 양 옆의 요소를 각 L, R이라 했을 때 은 L-abs(k), R-abs(k)로 동시에 변한다
!! 이렇다면 전체 합은 변하지 않는다
- k가 음수일 때, 양수로 변환 (2k) + 양옆 빼줌 (-2k) = 0
- k가 양수일 때는 magic move 미적용 (문제 조건)
모든 bank가 0 이상으로 만들기 위한 최소한의 magic move 횟수를 구하라는게 문제
아이디어 도출
a. 패턴 분석
- 0, 1, 2, ... idx에 순서대로 magic move 적용한다면?
ex) 1 -2 -1 3 [1] 1 -1 -2 1
-1 2 -3 3 [2] -1 1 -2 1
-1 -1 3 0 [3] -1 -2 1 1
1 -2 3 -1 [0] 1 -1 2 1
-1 2 1 -1 [1] -1 1 2 1
1 1 1 -2 [0] 1 2 3 1
-1 1 -1 2 [3] -1 0 -1 1
1 0 -1 1 [0] 1 1 0 1
1 -1 1 0 [1] 1 0 1 1
0 1 0 0 0 1 1 1
[일반 arr 적용] [누적합 적용]
총 9번 움직임
--> ! 누적합 arr에서 움직임이 규칙을 갖고 있는 듯 하다
b. Prefix_sum arr 움직임 파악
ex) [a, -2k, b, c, d] (a, b, c, k, d > 0)
- 일반 : [a-k, 2k, b-k, c, d]
누적 : [a-k, a+k, a+b, a+b+c, a+b+c+d]
--> idx-1, idx만 영향 받고, 나머지는 그대로
ex) [-2k, a, b, c, d] (a, b, c, k, d > 0)
- 일반 : [2k, a-k, b, c, d-k]
- 누적 : [2k, a+k, a+b+k, a+b+c+k, a+b+c+d]
--> idx ~ N-1 까지 영향받음
ex) [a, b, c, d, -2k] (a, b, c, k, d > 0)
- 일반 : [2k, a-k, b, c, d-k]
- 누적 : [2k, a+k, a+b+k, a+b+c+k, a+b+c+d]
--> idx ~ N-1 까지 영향받음
누적합이라는 힌트를 듣고 살펴봤는데, 문제 풀이를 어떻게 진행해야 할 지 잘 보이지 않는다
필요한 것이 무엇일까...
검증해야 할 사항
1. 음수인 걸 계속 뒤집다보면, 값이 나오는가
--> Simulate 해보니, 누적합 arr 마지막이 0보다 크면, 값이 나오는 게 보장될 것 같다 (추정)
2. 최소가 되는 방법은 어떻게 구하는가
--> 완전탐색을 통해 가능 : 1000000% 시간 초과
--> 절댓값이 큰 음수부터 magic move : 언젠간 수렴하므로, 값은 나올는데 최소값이 항상 나오는가는 모르겠다
--> 절댓값이 작은 음수부터 magic move : [2, 1, 0, 2, 1, 3, 0, 2, 1]로 idx 뒤집으면 됨
! 이것도 최소를 가지네?
3. 그렇다면 순서에 상관없이 최솟값이 나옴이 보장되는가?
- 만약 그렇다면, 구해지는 값이 최소값이 된다
--> 증명은 어떻게?
힌트 1 : 책 - Problem Solving Strategies; Chapter 1 - E9
모르겠어서 Problem Solving 책을 찾아봤다.
PSS - E9 요약 (IMO - 1986; solution 3)
f(x1, x2, x3, x4 ,x5) = (i=1~5) Σ (Xi - Xi+2)^2 (x6 = x1, x7 = x2)
위 식을 적용해보자
1. Magic Move 적용 전 : [a, -k, b, c, d]
=> (a-b)^2 + (c+k)^2 + (b-d)^2 + (a-c)^2 + (d+k)^2
2. Magic Move 적용 후 : [a-k, k, b-k, c, d]
=> (a-b)^2 + (c-k)^2 + (b-d-k)^2 + (a-c-k)^2 + (d-k)^2
[1] - [2] = (소거) + (4kc) + (2k(b-d) - k^2) + (2k(a-c) - k^2) + 4kd
= -2k^2 + 4ck + 4dk + 2k(a+b) - 2k(c+d)
= 2k( -k + 2c + 2d + a + b - c - d )
= 2k( a + b + c + d - k )
위 식이 항상 0보다 큰가?
i) 2k > 0 ?
- k는 양수이므로, 0보다 크다
ii) a+b+c+d-k > 0 ?
- 문제 조건이므로, 항상 0보다 큼이 보장된다
따라서 f(x1, x2, x3, x4, x5)는 수렴한다는 사실을 알 수 있다.
위의 내용을 간략하게 말하면, data variance가 작아지는 쪽으로 계속 수렴하므로,
step을 반복하다보면 언젠가는 모든 항이 음의 정수가 아닌 수로 변한다는 것이다.
책의 마지막 구절엔 다음 문장이 쓰여있다.
Remark. It is interesting to find a formula with the computer,
which, for input a, b, c, d, e, gives the number of steps until stop.
This can be done without much effort if s = 1.
For instance, the input (n, n, 1 — 4n, n, n) gives the step number f(n) = 20n - 10.
진짜인지 확인해보자
ex)
[ 1, 1, -3, 1, 1] [2]
[ 1, -2, 3, -2, 1] [1]
[-1, 2, 1, -2, 1] [0]
[ 1, 1, 1, -2, 0] [3]
[ 1, 1, -1, 2, -2] [2]
[ 1, 0, 1, 1, -2] [4]
[-1, 0, 1, -1, 2] [1]
[ 1, -1, 1, -1, 1] [1]
[ 0, 1, 0, -1, 1] [3]
[ 0, 1, -1, 1, 0] [2]
[ 0, 0, 1, 0, 0]
--> 10번의 move // 진짜네?
그럼 (n, n, 1 - 4n, n, n) 모양으로 만드는 것이 목표가 되는가? --> 가능하진 않을듯
(n, n, -4n, n, n) 인 경우엔?
[ 1, 1, -4, 1, 1]
[ 1, -3, 4, -3, 1]
[-2, 3, 1, -3, 1]
[ 2, 1, 1, -3, -1]
[ 2, 1, -2, 3, -4]
[ 2, -1, 2, 1, -4]
[ 1, 1, 1, 1, -4]
! 반복된다 --> 그래서 최초 누적합이 1 이상인 걸 문제조건에서 주는거구나
PSS 책에서 다음과 같은 구절이 있다.
Consider the infinite multiset S of all sums defined by s(i, j) = x_i + ... + x_j-1 with 1 < i < 5 and j > i.
In this set, all elements but one either remain invariant or are switched with others.
Only s(4, 5) = x4 changes to -x4.
Thus, exactly one negative element of S changes to positive at each step.
식에서 주어진 조건대로 (with 1 < i < 5 and j > i) 진행해보자
[a, -k, b, c, d]의 multiset(pS)
pS(0, 1) = a | pS(1, 2) = -k | pS(2, 3) = b | pS(3, 4) = c | pS(4, 5) = d
pS(0, 2) = a-k | pS(1, 3) = b-k | pS(2, 4) = b+c | pS(3, 5) = c+d | ps(4, 6) = a+d
pS(0, 3) = a+b-k | pS(1, 4) = b+c-k | pS(2, 5) = b+c+d | pS(3, 6) = a+c+d | pS(4, 7) = a+d-k
pS(0, 4) = a+b+c-k | pS(1, 5) = b+c+d-k | pS(2, 6) = a+b+c+d | pS(3, 7) = a+c+d-k | pS(4, 8) = a+b+d-k
pS(0, 5) = a+b+c+d-k
[a-k, k, b-k, c, d] 의 multiset(cS)
cS(0, 1) = a-k | cS(1, 2) = k | cS(2, 3) = b-k | cS(3, 4) = c | cS(4, 5) = d
cS(0, 2) = a | cS(1, 3) = b | cS(2, 4) = b+c-k | cS(3, 5) = c+d | cS(4, 6) = a+d-k
cS(0, 3) = a+b-k | cS(1, 4) = b+c | cS(2, 5) = b+c+d-k | cS(3, 6) = a+c+d-k | cS(4, 7) = a+d
cS(0, 4) = a+b+c-k | cS(1, 5) = b+c+d | cS(2, 6) = a+b+c+d-2k | cS(3, 7) = a+c+d | cS(4, 8) = a+b+d-k
cS(0, 5) = a+b+c+d-k
magic move를 적용한 idx를 i라고 했을 때, idx-1, idx, idx+1이 포함된 multiSet의 변화를 관찰해보면
pS(0, 1) = cS(0, 2)
pS(1, 2) = -k
pS(2, 3) = cS(1, 3)
pS(3, 4) = cS(3, 4)
pS(4, 5) = cS(4, 5)
pS(0, 2) = cS(0, 1)
pS(1, 3) = cS(2, 3)
pS(2, 4) = cS(1, 4)
pS(3, 5) = cS(3, 5)
ps(4, 6) = cS(4, 7)
pS(0, 3) = cS(0, 3)
pS(1, 4) = cS(2, 4)
pS(2, 5) = cS(1, 5)
pS(3, 6) = cS(3, 7)
pS(4, 7) = cS(4, 6)
pS(0, 4) = cS(0, 4)
pS(1, 5) = cS(2, 5)
pS(2, 6) = a+b+c+d
pS(3, 7) = cS(3, 6)
pS(4, 8) = cS(4, 8)
pS(0, 5) = cS(0, 5)
사용 안 된 pS
pS(1, 2) = -k --> 음수
pS(2, 6) = a+b+c+d --> a+b+c+d > k 이므로, 양수
사용 안 된 cS
cS(1, 2) = k --> 양수
cS(2, 6) = a+b+c+d-2k --> 조건에 따라 다름
조건을 따져보자
i) a+b+c+d >= 2k
- cS는 양수이므로, 음수 multiSet이 하나 줄어듦
ii) 2k > a+b+c+d
- cS는 음수이므로, 음수 multiSet이 유지됨[1, -1, 2, -3, 2]
a + b + c + d = 2
k = 1
--> 음수 multiset이 줄어든다
1 -1 2 -3 2
0 1 -1 -1 3
2 -2 1 0 2
-1 0 2 -1 4
1
--> -1 -3 -1 -1 -2 -1 -1
합 : -10, 개수 : 7
[0, 1, 1, -3, 2]
0 1 1 -3 2
1 2 -2 -1 2
2 -1 0 -1 3
-1 1 0 0 4
1
--> -3 -2 -1 -1 -1 -1
합 : -9, 개수 : 6
[0, 1, -2, 3, -1]
0 1 -2 3 -1
1 -1 1 2 -1
-1 2 0 2 0
2 1 0 3 -2
1
--> -2 -1 -1 -1 -1 -2
합 : -8, 개수 : 6
위의 예시에서,
magic move를 적용할 음수를 k라고 할 때,
음수를 제외한 나머지의 합 >= |2k| 일 때는 개수가 줄어든다.
지금 보니 합이 1씩 줄어드는 데, 이걸 증명할 수 있나?
다시 식을 정리해서 보면
사용 안 된 pS
pS(1, 2) = -k
pS(2, 6) = (a+b+c+d-k)+k
사용 안 된 cS
cS(1, 2) = k
cS(2, 6) = (a+b+c+d-k)-k
a+b+c+d-k > 0 이므로, cS(2, 6)은 -k보다 무조건 커진다
!!!! 모든 multiSet이 음수가 아닌 정수가 될 때, stop이 될 것이다
"음수"에만 집중해서 보면, 다음과 같은 걸 알아낼 수 있다
-k -> (a+b+c+d-k)-k -> (a+b+c+d-k)x2 -k -> ..
언젠간 0 이상이 되는 날이 온다
다른 음수에 대해서도 마찬가지
그러면 전체 누적합(a+b+c+d-k)과 음수에 대한 관계식이 나온다
.
.
일단 -k에 대해서 먼저 살펴보자
(a+b+c+d-k)*n -k > 0 이 되게 하는 n에 대하여
n > k / (a+b+c+d-k) 로 식을 바꿀 수 있을 것이고, n은 정수이므로
제일 작은 n에 대한 식은 n = ceil(k / (a+b+c+d-k)) + 1 로 말할 수 있다.
arr의 모든 multiSet에서, 합이 음수인 set을 k1, k2, k3, ..., kn 이라고 하자
일반식은 어떻게 도출되는가?
예시를 한 번 까보자
ex)
[-2, 4, -4, 5] [0]
[ 2, 2, -4, 3] [2]
[ 2, -2, 4, -1] [1]
[ 0, 2, 2, -1] [3]
[-1, 2, 1, 1] [0]
[ 1, 1, 0, 0]
필요한 magic move는 총 5번
multiSet을 까보면,
i) Magic move 0번 - [-2, 4, -4, 5]
-2 4 -4 5
2 0 1 3
-2 5 -1 7
3
-2 -4 -2 -1
합 : -9, 개수 : 4
ii) Magic move 1번 - [ 2, 2, -4, 3]
2 2 -4 3
4 -2 -1 5
0 1 1 7
3
-2, -4, -1 (-2에 전체 누적합 +3이 더해져 사라짐)
합 : -7, 개수 : 3
iii) Magic move 2번 - [ 2, -2, 4, -1]
2 -2 4 -1
0 2 3 1
4 1 5 -1
3
-2 -1 -1 (-4에 전체 누적합 +3이 더해져 -1이 됨)
합 : -4, 개수 : 3
iv) Magic move 3번 - [ 0, 2, 2, -1]
0 2 2 -1
2 4 1 -1
4 3 1 1
3
-1 -1 (-2에 전체 누적합 +3이 더해져 사라짐)
합 : -2, 개수 : 2
v) Magic move 4번 - [-1, 2, 1, 1]
-1 2 1 1
1 3 2 0
2 4 1 2
3
-1 (-1에 전체 누적합 +3이 더해져 사라짐)
합 : -1, 개수 : 1
위의 예시로 인해, multiSet에 관련된 일반식을 확실하게 세울 수 있다.
전체 multiSet 중, 요소의 합이 음수인 것을 k1, k2, k3, ..., kn이라고 해보자
arr 전체 누적합을 S라고 했을 때,
Minimum Number of Magic Move = (i=1 ~ n)Σ ceil(abs(ki)/S)
아래는 코드다
더보기
"""
@ 설계
1. 모든 multiSet에 대한 값을 구함
2. 전체 누적합을 구함
3. 음수인 multiSet만 찾음
4. 일반화 식을 적용해 magic move를 찾음
위의 경우, 시간복잡도를 따져보면
[1] 0 < n < 10,000
[2] -32,000 < k < 32,000
1. 모든 multiSet = N^2 = 100 000 000
2. 전체 누적합은 1의 마지막에 구해짐
3. 1의 과정에서 음수인 multiSet만 뺄 수 있음
4. 음수 multiSet에서, 식을 대입해 적용
1을 구할 때 누적합을 이용해야 안 터진다
@ 구현
[a, b, c, d, e] 의 multiSet을 구하는 예시를 보면,
a | a+b | a+b+c | a+b+c+d | a+b+c+d+e
b | b+c | b+c+d | b+c+d+e | b+c+d+e+a
c | c+d | c+d+e | c+d+e+a | c+d+e+a+b
d | d+e | d+e+a | d+e+a+b | d+e+a+b+c
e | e+a | e+a+b | e+a+b+c | e+a+b+c+d
각 행의 prefix sum을 구하면 된다, 마지막 전체 누적합은 항상 양수이므로 탐색할 필요 없다
"""
from math import ceil
N = int(input())
arr = list(map(int, input().split()))
S = sum(arr)
arr = arr*2
ans = 0
for i in range(N):
prefix = arr[i]
for j in range(N-1):
if j != 0:
prefix += arr[i+j]
if prefix < 0:
ans += ceil(-prefix/S)
print(ans)