문제
https://www.acmicpc.net/problem/22869
접근
- 1번째 돌에서 N번째 돌까지의 돌들에 대해, 돌을 한번 건너갈 때마다 쓸 수 있는 힘이 K를 넘지 않는 경로가 존재하기만 하면 되는 문제
- 따라서 i번째 돌까지 이동하는 데 필요한 힘의 최댓값의 최솟값을 저장할 배열을 만들고 DP로 풀이했다.
풀이
- d[i]를 i번째 돌까지 이동하는 데 필요한 힘의 최댓값의 최솟값으로 정의했을 때
- 점화식 d[i] = min(d[i], max(d[j], (j - i) * (1 + |ai - aj|))) for j st j < i 로 정의할 수 있다.
- 배열은 1번째 돌에서 i번째 돌로 건너뛸 때 필요한 힘으로 초기화한다.
n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
# (j - i) * (1 + |ai - aj|)
# d[i]: i번째 돌까지 이동하는데 필요한 힘의 최댓값의 최솟값
# d[i] = min(d[i], max(d[j], (j - i) * (1 + |ai - aj|))) for j st j < i
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]))))
print("YES" if d[n] <= k else "NO")
'Python > Coding Test' 카테고리의 다른 글
19641 중첩 집합 모델 (0) | 2022.02.28 |
---|---|
22871 징검다리 건너기 (large) (0) | 2022.02.27 |
1863 스카이라인 쉬운거 (0) | 2022.02.26 |
20182 골목 대장 호석 - 효율성 1 (0) | 2022.02.25 |
21277 짠돌이 호석 (0) | 2022.02.24 |