[프로그래머스 lv2] 2xn 타일링 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

2 x n 타일을 채우는 방법은 크게 두가지로 나눌 수 있다.

첫째, 2 x (n-1) 을 채우고 2 x 1 을 채우는 방법

 

 

 

둘째, 2 x (n-2)를 채우고, 1 x 2 를 가로로 두개 채우는 방법

 

 

따라서, dp[i] 를 2 x i 를 채우는 방법의 수라고 정의할 때, 점화식은 다음과 같다.

 

dp[i] = dp[i-1] + dp[i-2] 

 

이때, 문제에서 1000000007로 나눈 나머지를 구하라고 했으므로, 최종 점화식은 다음과 같다.

 

dp[i] = (dp[i-1] + dp[i-2]) % 1000000007

 

dp 값을 구한 뒤 dp[n]을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

using namespace std;

int solution(int n) {
    
    int dp[60005];
    
    dp[1] = 1;
    dp[2] = 2;
    for (int i=3; i<=n; i++) 
        dp[i] = (dp[i-1]+dp[i-2])%1000000007;
    return dp[n];
}