22871번: 징검다리 건너기 (large)
$N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으
www.acmicpc.net
문제
개의 돌에는 수 로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다.
개의 돌이 일렬로 나열 되어 있다.- 항상 오른쪽으로만 이동가능하다.
- 번째 돌로 이동할 때 × (1 + | |) 만큼 힘을 쓴다. 번째 돌에서
- 돌을 한번 건너갈 때마다 쓸 수 있는 힘은 최대 이다.
가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 의 최솟값을 구해보자.
입력
첫 번째 줄에 돌의 개수 이 공백으로 구분되어 주어진다.
두 번째 줄에는 개의 돌의 수 가 공백으로 구분되어 주어진다.
출력
가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 가능한 의 최솟값을 출력한다.
제한
코드
import sys
input = sys.stdin.readline
n = int(input())
stones = list(map(int, input().split()))
def power(i, j):
return (i - j)*(1 + abs(stones[i]-stones[j]))
dp = [int(1e9)] * n
dp[0] = 0
for i in range(1, n):
for j in range(i):
# j번째 돌을 밟고 i번째 돌로 가기
dp[i] = min(max(dp[j], power(i, j)), dp[i])
print(dp[n-1])
위 코드는 Python3로는 시간 초과가 발생하지만 PyPy3로는 통과 가능하다.
dp[i]에는 i번째 돌까지 가는데 필요한 K의 최소값이 저장된다.
dp[i]의 값을 j의 값을 1씩 증가시켜가며 max(dp[j], power(i, j)) 값과 비교하여 계속 갱신하여 준다. 이 값과 비교하는 이유는 0~j번째 돌까지 오는데 필요한 K의 최소값은 이미 dp[j]에 저장되어 있고 j번째 돌에서 바로 i번째 돌로 가는데 필요한 힘이 power(i, j)이다. 그러므로 j번째 돌을 밟고 i번째 돌로 가는데 필요한 k의 최소값은 이 둘 중 큰 값이 될 수 밖에 없다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 2293번 동전 1 (0) | 2023.05.29 |
---|---|
[Python/파이썬] 백준 1106번 호텔 (0) | 2023.05.28 |
[Python/파이썬] 백준 2624번 동전 바꿔주기 (0) | 2023.04.15 |
[Python/파이썬] 백준 5557번 1학년 (0) | 2023.04.15 |
[Python/파이썬] 백준 2225번 합분해 (1) | 2023.04.15 |