📖 문제
https://www.acmicpc.net/problem/22869
💻 내 코드
n, k = map(int, input().split())
mlist=list(map(int, input().split()))
dp=[0]*(n)
dp[0]=1
for i in range(n-1):
if dp[i]==0:
continue
for j in range(i+1,n):
jump=(j-i)*(1+abs(mlist[i]-mlist[j]))
if jump<=k:
dp[j]=1
if dp[-1]==1:
print("YES")
else:
print("NO")
💡 풀이
- 다이나믹 프로그래밍 이용
- dp리스트의 크기를 n만큼 만들어 둔다
- 갈 수 있는 곳을 1로 바꾸는 방법으로 해 나가면 된다
- 1번 돌은 무조건 가야 하므로 dp[0]=1
- 1번 돌 부터 출발해서 k이하의 힘으로 갈 수 있는 곳은 dp리스트에서 1로 바꿔둔다
- 만약 1번에서 출발했을 때의 경우를 다 계산 한 뒤 dp[i]이 0이라면 무조건 갈 수 없는 곳이므로 제외하고 계산한다
- 루프를 모두 돌고 난 뒤 dp[-1]이 1이라면 갈 수 있다는 뜻이므로 YES 출력
