Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 누룽지소금빵
- DIY
- 눈알빠지겠네
- 뜨아거
- 밥먹고
- 나쫌
- 코테
- 맛집
- 메일우유
- 알고리즘테스트
- 토이프로젝트
- javascript
- 취미
- LeetCode
- 서울제빵소
- 미앤아이
- 노노그램
- 바질토마토뭐시기
- 3d퍼즐
- 발더스게이트
- 코딩테스트
- 송리단
- 게임
- 발더스3
- 하스스톤
- 버즈2프로
- 잠실새내
- 발더스모드
- 천등
- 메탈퍼즐
Archives
- Today
- Total
.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 |
Comments