[프로그래머스 Level 2] 2 x n 타일링
1분 읽기
풀이 1: Bottom-Up 방식
function solution(n) {
const table = new Array(n-1);
const modular = 1000000007;
table[0] = 1;
table[1] = 2;
for(let i = 2; i <= n; i++){
table[i] = (table[i-1] + table[i-2]) % modular;
}
return table[n-1]
}풀이 2: Bottom-Up 방식 - 공간 복잡도 개선
function solution(n) {
const modular = 1000000007;
let a = 1;
let b = 2;
let temp;
for (let i = 2; i < n; i++) {
temp = (a + b) % modular;
a = b;
b = temp;
}
return b;
}Review
제한사항
- 가로의 길이 n은 60,000이하의 자연수 입니다.
- 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
DP8편 중 4번째
관련 글
4분 읽기
소수 구하기
소수 판별법과 소수를 구하는 알고리즘을 정리합니다.
1분 읽기
[프로그래머스 Level 2] 미로 탈출
프로그래머스 미로 탈출을 BFS로 풀이합니다.
1분 읽기
[프로그래머스 Level 2] 마법의 엘리베이터
프로그래머스 마법의 엘리베이터를 자리수 그리디로 풀이합니다.