Solution (DP)
# ๋งค๋ฒ 1๊ณ๋จ, 2๊ณ๋จ ์ฌ๋ผ๊ฐ ์ ์์
# ์ ์๊น์ง ์ฌ๋ผ๊ฐ ์ ์๋ ๋ฐฉ๋ฒ์ ๋ช ๊ฐ์ง์ธ์ง ๊ตฌํ์!
class Solution:
# DP ๋ฐฉ์
# ์๊ฐ ๋ณต์ก๋: O(N)
# Runtime: 31ms
# Beats: 66.32%
def climbStairs(self, n: int) -> int:
# ์ค์ ๋ก n์ 1, 2, 3, 4, 5 ์ญ ์ ๊ณ ํ๋์ฉ ๊ฒฝ์ฐ์ ์๋ฅผ ์ธ๋ณด์
# 1: 1, 2: 2, 3: 3(2 + 1), 4: 5(2 + 3), 5: 8(3 + 5)
# ๊ทธ๋ผ ์์ ๊ฐ์ด ๋ฌด์ธ๊ฐ์ ๊ท์น์ด ์๊น -> ์ด๋ฅผ ์๋์ ๊ฐ์ด dp์ "์ ํ์"์ผ๋ก ํํํ ์ ์์
# f(n) = f(n - 1) + f(n - 2)
# ์ฒซ๋ฒ์งธ ๊ณ๋จ์ ๊ฒฝ์ฐ์ ์์ ๋๋ฒ์งธ ๊ณ๋จ์ ๊ฒฝ์ฐ์ ์๋ฅผ ๋์
๋๋ฆฌ์ ์ ์ฅ (์ ํ์์ผ๋ก ์จ์ค์ผ ํ๋ 2๊ฐ)
f = dict()
f[1] = 1
f[2] = 2
# ์ ํ์์์ for๋ฌธ์ ๋ณดํต 3๋ถํฐ ์์ํ๊ณ n๊น์ง์ ๋ฐ๋ณต๋ฌธ์ผ๋ก ๋ง๋ค์ด์ค
# 3๋ฒ์งธ ๊ณ๋จ๋ถํฐ ์ถ๋ฐํ๊ณ , ์ ํ์์ด n - 2๋ถํฐ n๊น์ง๋๊น
for i in range(3, n + 1):
f[i] = f[i - 1] + f[i - 2]
return f[n]
Solution (Memorization)
class Solution:
# Memorization ๋ฐฉ์ (dp์ฒ๋ผ ๋ชจ๋ ๊ณ๋จ์ ์๋ฅผ ๋ค ๊ตฌํ ํ์๊ฐ ์ฌ์ค ์์)
# ๊ทธ๋๊น dp ๋ฐฉ์์์๋ for๋ฌธ์ผ๋ก ์ ์ฒด์ ๊ณ๋จ์ ๋ค ๋ ๋ค์์ ๊ฒฐ์ ์ ํ๋๊น
# ์ด ๋ฐฉ์์์๋ ๋ฐฉ๋ฒ ์๊ฐ ๊ตฌํด์ง๋ฉด ๊ทธ ์์ ์๋ ๊ณ๋จ์ ๊ณ์ฐํ ํ์๊ฐ ์๋ ๊ฑฐ์ง
# ์๊ฐ ๋ณต์ก๋: O(N)
# Runtime: 31ms
# Beats: 66.32%
def climbStairs(self, n: int) -> int:
# n์ด 1๊ณผ 2์ผ ๋๋ ์๋์ n - 2 ๊ฐ์ด ์์๊ฐ ๋๋ฏ๋ก ์
๋ ฅํ n์ด ๊ทธ๋๋ก ๋ฐํ๋๋๋ก ์ฒ๋ฆฌ
if n < 3:
return n
# ์ด์ ๊ณผ ํ์ฌ๋ฅผ ๊ฐ๊ฐ ์ฒซ๋ฒ์งธ, ๋๋ฒ์งธ ๊ณ๋จ์ ๊ฒฝ์ฐ์ ์๋ก ์ ์ฅ
before, current = 1, 2
# ์ธ๋ฒ์งธ ๊ณ๋จ๋ถํฐ ๊ตฌํ๋ ๋ก์ง
# Memorization์ ์งํํ์ฌ ํ์ฌ์ ์ด์ ๋ณ์๋ง ๊ณ์ ์ ์ฅํ์ฌ ๋๋ ค์ฃผ๋ ๊ฑฐ์ง
# ๊ทธ๋์ n - 2๋ฒ์งธ๊น์ง ๋์์ฃผ๋ ๊ฑฐ๊ณ
for _ in range(n - 2):
# ์ด๋ ๊ฒ ํ๋ฒ์ ์์ฑํ์ง ์์ผ๋ฉด ์์ ๋ค๋ฅธ ๋ก์ง์
# ๋ง์ฝ ์๋ ์ฒ๋ผ ์์ฑํ๋ค๋ฉด
# before = current
# current = before + current
# before์ด current ๋ณ์๋ก ์ ์ฅ์ด ๋ ํ, current์ ๋ ์ ์ฅ์ ํ๊ฒ ๋๋ ๊ฑฐ๋๊น
# ์์ ํ ์๋ชป๋ ๋ก์ง์ผ๋ก ๋ฐ๋
before, current = current, before + current
return current
Leave a comment