👀 문제
https://programmers.co.kr/learn/courses/30/lessons/12900
👊 도전
1. 설계
- n이 60,000이하의 자연수이기 때문에 DFS로 모든 경우를 체크할 수는 없다.
- DP를 이용해 점화식을 구해 문제를 해결한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
import java.util.Map.Entry;
/**
*
* @author HEESOO
*
*/
class Solution {
public int solution(int n) {
if(n==1 || n==2) return n;
int mod=1000000007;
int[] dp=new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=(dp[i-1]+dp[i-2])%mod;
}
return dp[n]%mod;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- DP를 이용한다
- 타일은
dp[i]=dp[i-1]+dp[i-2]을 만족한다. - 이때 더할 때 mod로 나눠 int형 범위를 초과하지 않게 하고, 계산 속도를 줄인다(숫자가 커질수록 계산하는데 시간이 많이 걸린다).
- 타일은