문제
https://www.acmicpc.net/problem/22871
접근
- 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)
'Python > Coding Test' 카테고리의 다른 글
4803 트리 (0) | 2022.03.01 |
---|---|
19641 중첩 집합 모델 (0) | 2022.02.28 |
22869 징검다리 건너기 (small) (0) | 2022.02.27 |
1863 스카이라인 쉬운거 (0) | 2022.02.26 |
20182 골목 대장 호석 - 효율성 1 (0) | 2022.02.25 |