-
[BOJ]백준 11060번: 점프 점프Problem Solving/BOJ(백준) 2021. 1. 9. 23:52
전형적인 DP문제이다
iteraton을 이용해서 구현하되, 현재 칸에서 이동 가능한 칸 중 최소 점프 수를 갱신할 수 있다면 해준다
n=int(input()) arr=list(map(int,input().split())) dp=[987654321 for _ in range(n+1)] dp[0]=0 for i in range(len(arr)): for j in range(i+1,i+arr[i]+1): if j >=n:break if dp[i]+1<dp[j]: dp[j]=dp[i]+1 if dp[n-1]!=987654321: print(dp[n-1]) else: print(-1)
Time complexity: O(n²)
😊
'Problem Solving > BOJ(백준)' 카테고리의 다른 글
[BOJ]백준 17928번: 오큰수/Stack (2) 2021.01.13 [BOJ]백준 1493번: 박스 채우기/DivideAndConquer (0) 2021.01.12 [BOJ]백준 11660번: 구간 합 구하기5/DP (413) 2021.01.05 [BOJ]백준 2504번: 괄호의값/Stack (0) 2021.01.04 [BOJ]백준 2665번: 미로 만들기/Dijkstra (0) 2020.12.29