[22871] 징검다리 건너기 (large) in python

https://www.acmicpc.net/problem/22871

22871번: 징검다리 건너기 (large)

이분 탐색으로 풀려다
실패하고 결국 다이나믹 프로그래밍으로 푼 문제다 ^0^
사실 이것도 구글링...해서
겨우 이해한 문제ㅜㅜㅜ

power=max(a,b) 이 부분이 이해가 되지 않아서
애를 먹었다.

a에 들어가는 건 j번째 -> i번째로 이동할 때 쓰여지는 힘
b에 들어갈 건 j번째까지 탐색을 진행했을 때
구해진 최소의 힘이다.

앞에서부터 탐색을 차례대로 진행하니까
i번째 앞부분은 이미 탐색이 끝난 상황이다.

a가 b보다 크다면 ?
-> b가 최소의 힘에 해당한다.
왜냐하면 b에는 j번째까지 탐색했을때의 최소의 값이 담겨있는데,
b보다 크면 이미 안되는 거다.
a에는 아까도 말했지만 dp[j-1]까지의 값이 들어가있지 않기 때문!

import sys

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
INF = 1e9
dp = [INF for _ in range(n)]

dp = [0] + [INF] * (n - 1)
for i in range(1, n):
    for j in range(0, i):
        power = max((i - j) * (1 + abs(A[i] - A[j])), dp[j])
        dp[i] = min(dp[i], power)
print(dp[n - 1])