22871 징검다리 건너기 (large)

문제

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

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

 

접근

• 22869 징검다리 건너기 (small) 문제랑 조건은 똑같고, N번째 돌까지 갈 수 있는 모든 경로 중 K의 최솟값을 찾는 문제이므로 파라메트릭 서치 즉, 이분탐색과 DP로 풀이했다.

 

풀이

• DP 과정은 22869번과 동일하고 lt는 0으로 rt는 10 ** 9으로 초기화한 후 이분탐색으로 적절한 K값중 가장 작은 값을 구했다.
• 비교 조건은 N번째 돌까지 이동하는데 필요한 힘의 최댓값의 최솟값이 mid 값보다 작거나 같으면 정답 갱신

n = int(input())
a = [0] + list(map(int, input().split()))

d = [0] * (n + 1)
for i in range(n + 1):
    d[i] = (i - 1) * (1 + abs(a[i] - a[1]))

for i in range(1, n + 1):
    for j in range(1, i):
        d[i] = min(d[i], max(d[j], (i - j) * (1 + abs(a[i] - a[j]))))

lt = 0
rt = 10 ** 9
ans = -1
while lt <= rt:
    mid = (lt + rt) // 2
    if d[n] <= mid:
        ans = mid
        rt = mid - 1
    else:
        lt = mid + 1
print(ans)