[Python] 31560: Balancing Bacteria

31560: Balancing Bacteria

USACO 2024 January Contest, Bronze
Problem 3. Balancing Bacteria

풀이

N <= 2*10⁵이므로, O(N²)으로 풀지 못한다.
끄적거리다 연립방정식 형태가 보여서 연립방정식을 통해 풀었다.

맨 오른쪽에서 스프레이를 뿌리므로, 왼쪽 풀부터 오른쪽으로 오면서 박테리아를 0으로 만들어야 한다. 각 풀의 박테리아 값을 0으로 만드는 스프레이 값을 왼쪽에서부터 a, b, c, ... 라고 하면 각 풀에 뿌려지는 스프레이 값은 다음과 같다.

값을 구하기 위해서는 a, b, c, d의 절댓값의 합을 구해야 한다.
연립방정식 형태로 바꿔보면

a = 1
2a + b = 3
3a + 2b + c = -2
4a + 3b + 2c + d = -7

각 식에서 위에 있는 식을 빼면
a = 1
a + b = 2
a + b + c = -5
a + b + c + d = -2

다시 각 식에서 위에 있는 식을 빼면
a = 1
b = 1
c = -7
d = 3

총 12번을 뿌리면 모든 박테리아 값을 0으로 만들 수 있다.

코드

import sys
input = lambda: sys.stdin.readline().strip()

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

for i in range(n - 1, 0, -1):
    arr[i] -= arr[i - 1]
for i in range(n - 1, 0, -1):
    arr[i] -= arr[i - 1]

print(sum(map(abs, arr)))

# 개선해봤는데 더 오래 걸리네
# import sys
# input = lambda: sys.stdin.readline().strip()

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

# print(sum(map(abs, arr)))