https://codeforces.com/contest/1525/problem/A
시간 2초, 메모리 256MB

input :

• n (2 ≤ n ≤ 5000)
• a1, a2, …, an (0 ≤ ai ≤ 1)

output :

• Print one integer — the minimum number of minutes you have to spend to achieve the following situation: every seat that was initially occupied must be free.
  맨 처음 차지했던 자리들은 비어 있어야 하는데 이러한 결과를 얻기까지 걸리는 시간의 최솟값을 출력하시오.

조건 :

• If the i-th armchair is occupied by someone and the j-th armchair is not, you can tell the person sitting in the i-th armchair to move to the j-th armchair.
  i번째 armchair에 앉아있는 사람이 있고 j번째는 그렇지 않을 때 이 사람을 옮긴다.

• The time it takes a person to move from the i-th armchair to the j-th one is |i−j| minutes.
  소요되는 시간은 |i - j|의 시간으로 본다.

---

7
1 0 0 1 0 0 1의 예시에서 보았을 때 1을 기준으로 가장 가까운 위치에 존재하는 빈 의자를 보면 되지 않나?

그러나, 수는 5000밖에 안 되고 1은 2500개가 최대이지만 최대의 경우에 모든 2500개에 대해 좌우로 확인을 해야한다. 이것의 시간 복잡도가 매우 크다.

문제의 풀이에서 원하는 것은 모든 경우를 확인하라는 것이다.
그러면 어떤 것을?

사람

사람의 수를 확인 할 수 있다. 빈 의자의 수도 확인 할 수 있고 그러면 이 둘을 우리는 데이터로 사용할 수 있는 것이다.

2차원 배열의 dp를 제작해서 행의 경우에는 몇 명의 사람이 자리에 앉아있는지
열의 경우에 어떤 의자까지 포함을 했는지 해서 각 값은 이동에 필요한 시간을 가지고 있게 하는 것이다.

빈 의자

앉을 수 있는 모든 의자의 경우를 따져야 한다. 그렇기에 dp를 사용하는 것이다.
그러면 인제 점화식을 따져야 하는데 맨 처음 1명이 의자를 앉는 경우에는 의자를 추가하기 전에 값을 가져오거나 현 위치에서 이동하는데 걸리는 시간을 비교한다.

의자를 추가하기 전의 값이 가능한 경우는 이미 n - 1개의 의자를 썼을 때 얻은 값이 더 작은데 이를 바꿀 이유가 없으니까 그렇다.

점화식

i명의 사람이 있을 때 j개의 빈 의자를 제공하면 걸리는 시간.
dp[i][j] = min(dp[i - 1][j - 1] + abs(position_of_person - vacant_chair), dp[i][j - 1])
위의 두 경우를 비교해야 한다. 사람과 빈 의자가 각각 1개씩 추가 되었다고 생각하면 되기 때문에 그러니까 이미 다른 사람들의 위치는 채워졌으니까 추가 되는 사람은 새로운 의자에 앉히는 것이다.
근데 이게 크다면 그냥 그 전의 의자를 추가할 때 얻은 값을 사용한다.

import sys

n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
occupied = []
vacant = []

for idx, item in enumerate(data):
    if item == 1:
        occupied.append(idx + 1)
    else:
        vacant.append(idx + 1)

if not occupied:
    print(0)
    exit(0)

dp = [[float('INF')] * (len(vacant) + 1) for i in range(len(occupied) + 1)]

for j in range(len(vacant)):
    dp[1][j + 1] = min(dp[1][j], abs(occupied[0] - vacant[j]))

for i in range(1, len(occupied)):
    for j in range(i, len(vacant)):
        dp[i + 1][j + 1] = min(dp[i][j] + abs(occupied[i] - vacant[j]), dp[i + 1][j])
print(dp[-1][-1])