45. Jump Game II

LeetCode 갤러리
마이너

자동 짤방 이미지

이미지가 없습니다.

자동 짤방으로 사용할 이미지를 등록해 주세요.

Eat, Sleep, LeetCode, Repeat

매니저

부재중입니다.(ddakgun)

부매니저

흑화뉴비(coderhs)

개설일

2022-12-26

chromate00

2023.02.08 20:12:04

조회 22 추천 0 댓글 0

# @param {Integer[]} nums
# @return {Integer}
def jump(nums)
    last=0
    n=nums.size
    dp=[0]*n
    (0...n).each do|i|
        dp.fill(dp[i]+1,last+1..[n-1,i+nums[i]].min)
        last=[last,[n-1,i+nums[i]].min].max
    end
    dp[-1]
end

간단한 문제지만 이 풀이 방식이 그다지 간단하지는 않기 때문에 설명해 보겠습니다. 일단 기본적으로 현재 칸까지 횟수가 k고, 이 칸에서 p칸을 갈 수 있다고 합시다. 그런데 앞에 횟수가 k인 경로가 확정된 칸이 몇 칸 더 있다면 그 칸으로 가는 건 손해입니다. 따라서 값이 확정된 칸들 바로 뒤부터 갈 수 있는 가장 먼 위치까지 DP 배열을 갱신합니다. 또한, (1인 구간에서 우측으로 확장) -> (2인 구간에서 우측으로 확장) -> (3인 구간에서 우측으로 확장)과 같은 방식으로 진행되기 때문에, 어떤 위치에서 확정된 마지막 칸까지는 최대 1만큼 차이가 납니다. 그래서 이러한 방식으로 DP를 갱신해 줘도 결과는 동일하게 나오게 되며, 이때 시간복잡도는 O(n)입니다.

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	2025년 가장 기억에 남는 인터넷 이슈는?	운영자	25/12/22	-	-
155	45. Jump Game II	이벤트(1.226)	23.02.08	22	0
	45. Jump Game II	chromate00	23.02.08	22	0
153	45. Jump Game II	개발뉴비	23.02.08	28	0
151	904. Fruit Into Baskets	개발뉴비	23.02.08	33	0
148	904. Fruit Into Baskets	이벤트(1.226)	23.02.07	30	0
147	904. Fruit Into Baskets	chromate00	23.02.07	24	0
146	1470. Shuffle the Array	이벤트(1.226)	23.02.07	21	0
145	1470. Shuffle the Array	개발뉴비	23.02.06	34	0
143	1470. Shuffle the Array	chromate00	23.02.06	24	0
142	438. Find All Anagrams in a String	개발뉴비	23.02.05	33	0
141	438. Find All Anagrams in a String	chromate00	23.02.05	19	0
139	438. Find All Anagrams in a String	이벤트(1.226)	23.02.05	24	0
138	567. Permutation in String	개발뉴비	23.02.05	61	0
137	567. Permutation in String	이벤트(1.226)	23.02.04	23	0
136	567. Permutation in String [1]	chromate00	23.02.04	48	0
134	6. Zigzag Conversion.	chromate00	23.02.03	24	0
133	6. Zigzag Conversion	이벤트(1.226)	23.02.03	20	0
131	6. Zigzag Conversion	개발뉴비	23.02.03	30	0
130	953. Verifying an Alien Dictionary [1]	이벤트(1.226)	23.02.02	36	0
128	953. Verifying an Alien Dictionary	개발뉴비	23.02.02	42	0
127	953. Verifying an Alien Dictionary	chromate00	23.02.02	25	0
126	1071. Greatest Common Divisor of Strings	개발뉴비	23.02.02	28	0
125	1071. Greatest Common Divisor of Strings	이벤트(1.226)	23.02.01	37	0
123	1071. Greatest Common Divisor of Strings	chromate00	23.02.01	30	0
122	LeetCode 오늘의 문제 redirect 서비스	ㅇㅇ(1.229)	23.02.01	39	1
121	1626. Best Team With No Conflicts	이벤트(1.226)	23.01.31	25	0
119	1626. Best Team With No Conflicts [2]	chromate00	23.01.31	53	0
118	1137. N-th Tribonacci Number	개발뉴비	23.01.30	37	0
117	1137. N-th Tribonacci Number	이벤트(1.226)	23.01.30	19	0
116	1137. N-th Tribonacci Number	chromate00	23.01.30	22	0
113	352. Data Stream as Disjoint Intervals	개발뉴비	23.01.29	46	0
112	구글러에게 들은 코딩인터뷰 팁	ㅇㅇ(203.226)	23.01.28	64	0
111	352. Data Stream as Disjoint Intervals [1]	이벤트(219.251)	23.01.28	39	0
110	352. Data Stream as Disjoint Intervals [1]	chromate00	23.01.28	51	0
108	472. Concatenated Words [1]	이벤트(219.251)	23.01.28	38	0
106	472. Concatenated Words [1]	개발뉴비	23.01.28	57	0
104	하드라니 오늘 풀 수 있을까	ㅇㅇ(118.235)	23.01.27	45	0
103	472. Concatenated Words	chromate00	23.01.27	44	0
101	787. Cheapest Flights Within K Stops	개발뉴비	23.01.26	34	0
100	787. Cheapest Flights Within K Stops	이벤트(219.251)	23.01.26	35	0
97	787. Cheapest Flights Within K Stops	chromate00	23.01.26	42	0
96	2359. Find Closest Node to Given Two Nod	이벤트(219.251)	23.01.26	39	0
95	2359. Find Closest Node to Given Two ~ [1]	개발뉴비	23.01.26	38	0
92	이벤트 너무 어려운데 힌트 봐도 되나요 [1]	이벤트(39.7)	23.01.25	75	0
91	2359. Find Closest Node to Given Two Nod	chromate00	23.01.25	38	0
90	53. Maximum Subarray	크아아아앙	23.01.25	32	0
89	45. Jump Game II	크아아아앙	23.01.25	26	0
88	55. Jump Game	크아아아앙	23.01.25	42	0
87	909. Snake and Ladders	chromate00	23.01.24	71	0
86	909. Snakes and Ladders [1]	개발뉴비	23.01.24	56	0