알고리즘/프로그래머스
[프로그래머스] 2 x n 타일링 -Java
dkwjdi
2020. 12. 28. 16:04
https://programmers.co.kr/learn/courses/30/lessons/12900
코딩테스트 연습 - 2 x n 타일링
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는
programmers.co.kr
class Solution {
public int solution(int n) {
int answer = 1;
int a=1;
int b=1;
for(int i=1; i<n; i++) {
answer=(a+b)%1000000007;
a=b;
b=answer;
}
return answer;
}
}
소요시간 : 25분
dp문제입니다... dp는 항상 어렵습니다 ㅜㅜ
우선 점화식을 세우기 위해 n=5까지 직접 손으로 해보았습니다
n=1 -> 1
n=2 -> 2
n=3 -> 3
n=4 -> 5
n=5 -> 8
직접 해보니 피보나치가 딱 보였습니다!
사실 피보나치인것만 찾으면 코딩은 몇글자 되지도 않아서... 금방 풀 수 있는 문제 같습니다!