
์๊ฐ ๋ฐฉ์
dp๋ฌธ์ ์ ํ์ด๋ค
Minimum cost๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ฏ๋ก for loop์ผ๋ก dp์ ์ต์๊ฐ์ ์ ์ฅํด ์ฃผ๋ฉด ๋๋ค
ํ์ด ๊ณผ์
1๋ฒ์งธ ๊ณ๋จ์ด๋ 2๋ฒ์งธ ๊ณ๋จ์ ๋๋ฌํ๋ cost๋ 0์ด๋ค
dp[0] = dp[1] = 0
์? ์์์ index 0์ด๋ 1 ์๋ฌด ๊ณณ์์ ์์ํด๋ ๋๋ค๊ณ ํ๋๊น
๊ทธ๋ฌ๋ฏ๋ก index[2]๋ถํฐ ์ ์ฅ์ ์์ํด ์ฃผ๋ฉด ๋๋ค
๊ทธ๋์ 2์์ loop์ ์์ํ๋ฉด ๋ ๊ฒ์ด๊ณ , cost์ ๋ง์ง๋ง๊น์ง ๋๋ ค์ฃผ๋ ๊ฑธ loop์ ์กฐ๊ฑด์ผ๋ก ํด์ฃผ๋ฉด ๋ ๊ฒ์ด๋ค
* for loop์์๋ ๋ญ ์์ฑํด์ผํ๋๊ฐ?
๋น์ฐํ ๋ง์ด์ง๋ง dp์ ์ ์ฅ์ ๊ฐ์ ์ ์ฅํ๋ ์ฝ๋๋ฅผ ์ง์ฃผ๋ฉด ๋๋ค
ํ ๋ฒ์ one or two steps๋ฅผ ๊ฐ ์ ์๋ค๊ณ ๋ฌธ์ ์ ๋์์๋ค
๊ทธ๋ผ 2๋ฒ์งธ ๊ณ๋จ( i=3)์ ๊ฐ๋๋ฐ ๊ทธ๋ผ ์ด๋ค ๋ฐฉ์์ด ์๋๊ฐ?
1. 0๋ฒ์งธ ๊ณ๋จ์์ 2 steps
2. 1๋ฒ์งธ ๊ณ๋จ์์ 1 step
๊ทธ๋ ๋ค๋ฉด ์ฐ๋ฆฌ๋ ๋ ์ค์ ์ต์๊ฐ๋ง dp์ ์ ์ฅํด ์ฃผ๋ฉด ๋ ๊ฒ์ด๋ค
๐ป ์์ฑ ์ฝ๋
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
c = len(cost)
dp = [0] * (c+1)
for i in range(2, c+1):
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
return dp[c]
* dp[i-1] + cost[i-1] ๊ทธ๋ฆฌ๊ณ dp[i-2] + cost[i-2] ์ ๋ํ ์ค๋ช
๊ทธ๋ฆผ์ผ๋ก ๊ทธ๋ฆฌ๋ ๊ฒ ๊ธฐ์ต์ ๋ ๋จ์ผ๋๊น ๊ทธ๋ฆผ์ผ๋ก ํ ๋ฒ ์ค๋ช ์ ํด๋ณด๊ฒ ๋ค


i = 2์ผ ๋, 2๋ฒ ๊ณ๋จ์ผ๋ก ๋์ฐฉํ๋ ๋ฐฉ๋ฒ์ 2๊ฐ์ง๊ฐ ์กด์ฌํ๋ค (๊ทธ๋ฆผ ์ฐธ๊ณ )
0๋ฒ์งธ ๊ณ๋จ์์ 2๋ฒ์งธ ๊ณ๋จ์ผ๋ก ๊ฐ๋ cost๋ 10
1๋ฒ์งธ ๊ณ๋จ์์ 2๋ฒ์งธ ๊ณ๋จ์ผ๋ก ๊ฐ๋ cost๋ 15
์ด ๋ ๊ฐ์ง ๋ฐฉ๋ฒ ์ค์ ๊ฐ์ฅ ์ ์ cost๋ฅผ ์ฌ์ฉํ๋ ๊ฑด 10 ์ฆ ์ฒซ ๋ฒ์งธ ๋ฐฉ๋ฒ์ด๊ธฐ์ 10์ dp[2]์ ์ ์ฅํด ์ค๋ค
๋ง์ฐฌ๊ฐ์ง๋ก i = 3์ผ ๋,
1๋ฒ ๊ณ๋จ์์ 3๋ฒ ๊ณ๋จ์ ๋๋ฌํ๊ธฐ ์ํ cost๋ ์ผ๋ง? 15
2๋ฒ์์ 3๋ฒ์? 20์ธ๋ฐ ์ฌ๊ธฐ์ 2๋ฒ๊น์ง ๊ฐ๊ธฐ ์ํ ๊ฐ๋ ํฉ์ณ์ค์ผ ํ๋ค.
์? 2๋ฒ์ ์๋๋ถํฐ ์์ ์ ์๊ธฐ ๋๋ฌธ์
2๋ก ๊ฐ๋ ๊ฐ์ฅ ํจ์จ์ ์ธ cost๋ ์์ i = 2์ผ ๋ ๊ณ์ฐํ 10์ด๋ค
๊ทธ๋ผ 10 + 20 ํด์ 30์ด ๋์ค๋๋ฐ ๊ฐ์ฅ ํจ์จ์ ์ธ ๊ฑด 15๋ผ๋ cost๊ฐ ๋ ๋ค
๊ทธ๋์ dp[3]์๋ 15 ์ ์ฅํ๋ฉด ๋๋ค
i = 4์ผ ๋๋ ์ด ๊ธ์ ์ฝ๋ ๋ถ์ด ์ข ์ด์ ์ง์ ํ ๋ฒ ์จ๋ณด์๋ฉด ์ดํดํ๋ ๋ฐ ๋์์ด ๋ ๊ฒ ๊ฐ๋ค
๋ง์ง๋ง์ dp[c]๋ก ๋ฆฌํด์ ํด์ฃผ๋ ์ด์
๋ง์ง๋ง dp๊ฐ ์ฐ๋ฆฌ๊ฐ ์ ์ผ ์ ์ ๋น์ฉ์ผ๋ก top์ ๋๋ฌํ ์ ์๋ ๋น์ฉ์ด๋ค.
c๋ ์ฐ๋ฆฌ๊ฐ ๋ฐ์ list์ ์ด ๊ธธ์ด์ด๋ฏ๋ก ๋ง์ง๋ง c๋ ์ฐ๋ฆฌ์ ๋ง์ง๋ง index๊ฐ ๋๋ค.
๊ทธ๋์ test case [10,15,20,30]์ ๋ฃ์ผ๋ฉด ๊ฒฐ๊ณผ๋ dp[4], ์ฆ 30์ผ๋ก ๋์จ๋ค

ํธ๋ ๊ฒ๋ณด๋ค ์ดํดํ๋ ๊ฒ์ด ์ ์ผ ์ค์ํ๋ค
๋์ถฉ ์ดํดํ์ง ๋ง๊ณ ์ง์ง ํ๋ํ๋ ์๋๋ ์ง๋ฌธ์ ๊ฐ์ง๊ณ ์ ๊ทผ์ ํ๋ฉด ๋๋ฆฌ๊ฒ ์ง๋ง ์ฑ์ฅ์ ํ์คํ๊ฒ ์ง...?
์ดํดํ๋ฉด ์ด๋ ๊ฒ ๋ฌธ์ ํธ๋ ๊ณผ์ ์ด ๋น์ฐํด์ง๊ณ ์ต์ํด์ง ํ ๋๊น ์ด์ฌํ ํด๋ณด์
ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ ํ์ดํ !
'์ฝ๋ฉ ํ ์คํธ > leetcode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
| 55. Jump Game (Medium) [Python] (0) | 2024.02.04 |
|---|---|
| 53. Maximum Subarray (Medium) [Python] (0) | 2024.02.04 |
| 70. Climbing Stairs (Easy) [Python] (2) | 2024.02.03 |
| 49. Group Anagrams (Medium) [Python] (0) | 2024.02.03 |
| 1. Two Sum (Easy) [Python] (0) | 2024.02.03 |