[Python] leetcode45-Jump Game II

leetcode45-Jump Game II

leetcode45-Jump Game II

---

-	idx 0	idx 1	idx 2	idx 3	idx 4
nums	2	3	1	1	4
cntlist	0	float(‘inf’)	float(‘inf’)	float(‘inf’)	float(‘inf’)

cntlist

• 최소 jump 카운트를 저장하는 리스트
• 최소 jump 수를 구하기 위한 문제이므로 cntlist에는 최대 값인 inf (양의 무한대) 로 초기화 해 준다.

---

아래 Table은 cur index의 변화에 따른 cntlist(최소 jump 카운트)의 값 변화를 보여 준다.

-	-	idx 0	idx 1	idx 2	idx 3	idx 4
—	nums	2	3	1	1	4
—	cntlist	0	float(‘inf’)	float(‘inf’)	float(‘inf’)	float(‘inf’)
cntlist의 값 변화	—	—	—	—	—	—
		cur	cntlist[cur+1]	cntlist[cur+2]
cur = 0	nums[cur]->2	0	1	1	inf	inf
			cur	cntlist[cur+1]	cntlist[cur+2]	cntlist[cur+3]
cur = 1	nums[cur]->3	0	1	1	2	2
				cur	cntlist[cur+1]
cur = 2	nums[cur]->1	0	1	1	2	2
					cur	cntlist[cur+1]
cur = 3	nums[cur]->1	0	1	1	2	2
						cur
cur = 4	nums[cur]->4	0	1	1	2	2

최종 결과 Return

return cntlist[-1]

nums[cur+n] 컬럼 로직

if cntlist[cur] +1 < cntlist[cur+1]:	
    cntlist[cur+1] = cntlist[cur] +1	

풀이

class Solution:
    def jump(self, nums: List[int]) -> int:
        
        cntl = [float('inf')] *len(nums)
        cntl[0] = 0
        
        for cur in range(len(nums)):
            for j in range(1, nums[cur]+1):
                #print(cur,j)
                if cur + j >= len(nums): continue
                if cntl[cur] + 1 < cntl[cur+j]:
                    cntl[cur+j] = cntl[cur] + 1
        
        return cntl[-1]