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

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

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

---

 

-풀이-

dp로 풀면 된다. dp[i]=j 는 가로의 길이가 i일때, 놓을 수 있는 경우의 수를 j라고 하자

그럼 점화식은 dp[i]=dp[i-1]+dp[i-2]가 된다.

위의 그림처럼 i=4일땐, i가 3인 경우에 세로로 세운 작대기를 붙인 경우와, i가 2인 경우에 가로로 2개를 쌓은 경우의 수를 더해주면 된다. 따라서

dp[i]=dp[i-1]+dp[i-2]가 된다.

 

-시간복잡도-

n까지 탐색하므로 O(N)이 된다.

 

-코드-

#include <string>
#include <vector>
#define MOD 1000000007
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])%MOD;
    }
    answer=dp[n];
    
    return answer;
}