[프로그래머스 / Level 3] 2 x n 타일링

https://programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

문제 접근법

• 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다.
• 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다.
• DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2]가 성립한다.

아래는 코드입니다.

 

#include <string>
#include <vector>
 
using namespace std;
 
int dp[60001];
 
int solution(int n) {
    int answer = 0;
    
    dp[1] = 1;
    dp[2] = 2;
    
    for(int i = 3; i <= n; i++)
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
    
    answer = dp[n];
    
    return answer;
}