Notice
Recent Posts
Recent Comments
Link
.Zzumbong
[leetCode/JS] 70. Climbing Stairs ๋ณธ๋ฌธ
๋์ด๋ [ ๐ ] Easy
๋ฌธ์ ์ค๋ช
You are climbing a staircase. It takes n
steps to reach the top.
Each time you can either climb 1
or 2
steps. In how many distinct ways can you climb to the top?
n ๊ณ๋จ์ ์ฌ๋ผ๊ฐ๋๋ฐ, 1 ๋๋ 2์นธ ์ฉ ์ฌ๋ผ ๊ฐ ๋, ๋ชจ๋ ๊ฒฝ์ฐ์ ์๋ ์ผ๋ง์ธ๊ฐ?
์ ์ถ๋ ฅ ์
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
Constraints
1 <= n <= 45
๋ด ์๋ฃจ์
- ์์ ํผ๋ณด๋์ฐ ์๊ณ ๋ฆฌ์ฆ์ DP(Dynamic Programming)์ด ์ฐ์ธ๋ค.
- DP์ ๊ธฐ๋ณธ์ธ ํฐ ์์ ์ ํ๊ธฐ ์ํด ์์ ์์ ๋ถํฐ ๊ณ์ฐํ๋ค.๋ฅผ ์ ์ฉํ๋ฉด ๋๋ค.
- ๋ง์ฝ n = 1 ์ผ๋, 1๊ฐ [1]
- n = 2 ์ผ ๋, 2๊ฐ [1, 1], [2]
- n = 3 ์ผ ๋, 3๊ฐ [1, 1, 1], [1, 2], [2, 1]
- n = 4 ์ผ ๋, 5๊ฐ [1, 1, 1, 1], [1, 1, 2], [2, 1, 1], [1, 2, 1], [2, 2]
- n = 5 ์ผ ๋๋ [n-1] + [n-2] ์ธ 8์ด ๋๋ค.
- ๊ฒฐ๋ก ์ ์ผ๋ก ๊ณ๋จ 5๊ฐ๊ฐ ์์ ๋, ๊ณ๋จ, 4๊ฐ ์ผ๋์ 3๊ฐ ์ผ๋์ ๊ฒฝ์ฐ์ ์๋ฅผ ๋ํ๋ฉด 5๊ฐ์ ๊ฒฝ์ฐ์ ์๊ฐ ๋์จ๋ค.
- ์ ํ์์ผ๋ก ๋ณด๋ฉด
f(n) = f(n-1) + f(n-2)
๊ฐ ๋๋ค.
var climbStairs = function(n) {
if(n<3) return n;
const arr = [1, 1];
for (let i = 2; i <= n; i++) {
arr[i] = arr[i-1] + arr[i-2];
}
return arr[n];
};
๊ฐ์ํ
- ํผ๋ณด๋์ฐ ์๊ณ ๋ฆฌ์ฆ์ ๋ชป ํ์ด๋ดค๊ฑฐ๋ DP๋ฅผ ๋ชจ๋ฅด๋ฉด ๊ฐ๊ณ ์ํ๋ค.
- ์๋ฉด Easy! ๋ชจ๋ฅด๋ฉด ์ฏ.
var climbStairs = function(n) {
let two = 0, one = 1;
for (let i = 0; i < n; i++) {
[two, one] = [one, two + one];
}
return one;
};
- ์ฌ๋ฏธ์๋ ์ฝ๋๋ฅผ ์ฐพ์๋ค. ๋๋ฌด ์ํ๋ค ๋๋์ด์ผ.
'coding test > leetCode' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[leetCode/JS] 198. House Robber (0) | 2022.12.14 |
---|---|
[leetCode/JS] 931. Minimum Falling Path Sum (0) | 2022.12.13 |
[leetCode/JS] 124. Binary Tree Maximum Path Sum (0) | 2022.12.11 |
[leetCode/JS] 1339. Maximum Product of Splitted Binary Tree (0) | 2022.12.10 |
[leetCode/JS] 1026. Maximum Difference Between Node and Ancestor (0) | 2022.12.09 |
0 Comments