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

문제

프로그래머스

2 x 1의 타일을 가지고 2 x n의 바닥을 채우는 문제이다.

 

나의 풀이 전략

동적 계획법으로 푼다.

 

상세

바닥이 2 x 1이라면, 채우는 경우의 수는 1이다.

그림 1

 

바닥이 2 x 2이라면, 채우는 경우의 수는 2이다.

그림 2

그림 3

 

이제 이 두 가지 크기의 바닥을 기반으로 점화식을 세울 수 있다.

크기가 2 x n인 바닥을 채우는 경우의 수를 DP[n]이라 하자.

 

바닥이 2 x n이라면,

1)

먼저 2 x 1만큼 맨 오른쪽을 채운다. 그리고 나머지 왼쪽을 채운다.

 

그림 4

 

1)의 경우의 수는 바로 DP[n - 1]과 같다.

 

2)

먼저 2 x 2만큼 맨 오른쪽을 채운다. 그리고 나머지 왼쪽을 채운다.

그림 5

그림 6

그런데, 그림 5는 사실 그림 4의 경우에 포함된다. 그림 5는 무시해야 한다.

2)의 경우의 수는 DP[n - 2]와 같다.

 

따라서 DP[n]은 DP[n - 1]과 DP[n - 2]를 합한 것과 같다.

 

전체 소스코드

#include <memory.h>
using namespace std;

int solution(int n)
{
    int answer = 0;

    int DP[60001];
    memset(DP, 0, sizeof DP);

    DP[1] = 1;
    DP[2] = 2;

    for(int i = 3; i <= n; ++i)
        DP[i] = (DP[i - 2] + DP[i - 1])%1000000007; // 문제 제한사항

    answer = DP[n];

    return answer;
}