[ 프로그래머스 2 x n 타일링 (Lv3) ] (C++)

프로그래머스의 2xn타일링(Lv3) 문제이다.

[ 문제풀이 ]

먼저 규칙을 한번 찾아보자.

n = 1 일 경우를 보게 되면 한가지 경우밖에 존재하지 않는다.

n = 2 일 경우를 보게 되면 2가지 경우가 존재한다.

.

n = 3 일 경우를 보자.

.

위와 같이 3가지 경우가 존재한다.

즉 ! n = 3일 경우를 보게되면, 2x1짜리 타일로 만드는 경우 1가지 + 2x2짜리 2개와 2x1짜리 타일 1개로 만드는 경우 2가지

해서 총 3가지가 나오게 된다.

간단한 규칙을 찾아보게 되면 n의 값을 찾기 위해서는 n - 1로 만들 수 있는 경우의 수 + n - 2로 만들 수 있는 경우의 수

라는 것을 알 수 있다.

이런 규칙을 점화식으로 이용해서 Dynamic Programming방법으로 구현해 주었다.

주의해야 할 것은, 최종 결과값을 주어진 값으로 Moduler 연산을 진행해서 구해야 하는데, 구하는 중간과정에서 이미 int형의

범위를 넘을 수 있기 때문에, 중간중간 과정에서 Moduler 연산을 진행해 주어야 한다.

[ 소스코드 ]

#include<string>
#include<vector>
 
#define MODULER 1000000007
using namespace std;
 
int solution(int n)
{
    int Tile[60010] = { 0, };
    Tile[1] = 1;
    Tile[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        Tile[i] = (Tile[i - 2] + Tile[i - 1]) % MODULER;
    }
    return Tile[n];
}