[BOJ] 22781 징검다리 건너기 - Python

문제

---

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

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

 

풀이

---

 

문제를 처음 보면서 첫 번째 돌에서 마지막 돌까지 가는 모든 케이스(조합)를 체크해보면 답을 구할 수 있겠다라는 생각은 쉽게 떠올릴 수 있었습니다. 하지만 이러한 방법은 N의 크기와 시간 제한때문에 불가능함을 알 수 있습니다.

 

경험상 문제가 특정 원소를 선택하거나 하지않거나(이 문제의 경우 발판으로 특정 돌을 선택 할지 말지)같은 상황일 때 DP가 해답인 경우가 종종 있어서 DP로 생각을 바꿔보았습니다.

 

DP문제에서는 DP배열의 특정 인덱스가 무엇을 의미하는지를 정하는 것이 중요합니다.

풀이 코드에서 dp[i] 는 첫 번째 돌에서 i 번 째 돌까지 건너가는 모든 경우의 수 중 힘이 제일 적게 드는 경우의 값입니다.

 

dp[i]의 값을 아래와 같은 방법으로 할당해주면 i 번째 돌까지 가는 최소 힘을 구할 수 있습니다.

 

1. i  > j 인 모든 j 에 대하여 j 번째 돌을 밟고 i 번째 돌로 오는 경우를 생각해봅니다. 이때 드는 최소 힘은 j -> i로 갈때 드는 힘과 0 -> j 까지 오는데 드는 힘(dp[j]) 중 더 큰 힘이 될 것입니다.
2. 위의 과정을 j = 0 ~ (i - 1) 까지 모두 시행하면서 가장 최소값을 dp[i]에 넣어주면 이 값이 곧 첫 번째 돌에서 i 번 째 돌까지 가는데 드는 최소 힘이 됩니다.

 

1, 2 과정을 i = 1 ~ (n - 1) 까지 반복하여 dp배열을 전부 적절하게 할당시켜주면 dp[-1]이 곧 문제에서 요구한 정답이 됩니당!

 

이때 시간 복잡도는 O(n^2) 이고 n의 최댓값은 5000이므로 제한 시간 안에 충분히 연산이 가능합니다.

INF = 999999999
n = int(input())
A = list(map(int, input().split()))
# dp[i]는 i까지 가는데 드는 최소 힘
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[-1])