2 x n 타일링

문제 링크

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

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

 

문제 풀이 코드

#include <string>
#include <vector>

using namespace std;

const int MN=60001;
int dp[MN];

int solution(int n) {
    int answer = 0;
    dp[0]=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;
}

백준에서 똑같은 문제를 한번 풀어봐서 쉽게 풀 수 있었다.

손으로 경우의 수를 다 따져서 그려보면 피보나치 수임을 알 수 있다.

재귀함수가 아닌 dp방식으로 문제를 풀었다.