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

3 x n 의 직사각형에 2 x 1 짜리 타일을 채우는 방법의 개수를 구하는 문제입니다

문제

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

3 x 8 타일링 방법 중 하나

제한사항

• 가로의 길이 n은 5,000이하의 자연수 입니다
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요

입출력 예시

n	result
4	11
6	41

입출력 예 #1

다음과 같이 11가지 방법이 있다

n이 4일 때 채울 수 있는 경우

Solution

점화식

f(n) = f(n-2) * 3 + **f(n-4) *** 2 + f(n-6) * 2 + … + f(2) * 2 + 2

#include <string>
#include <vector>

using namespace std;

const int bound = 1000000007; // 나눌 숫자 미리 저장
long long dp [5001]; // 이전 계산 내용을 저장할 공간

long long process(int n) {
	if (n == 1) return 0; // n이 홀수에서는 2x1 타일로 채울 수 없음
	if (n == 2) return 3; // n이 2일때는 3가지의 경우의 수로 채울 수 있음 
	if (dp[n]) return dp[n]; // 저장된 값이 있다면 저장된 값을 불러오기
	else {
		dp[n] = 3 * process(n - 2); //재귀함수를 활용해 n-2 곱하기 3을 저장
		for (int i = 4; i < n; i += 2) {
			dp[n] += 2 * process(n - i); // 재귀함수를 통해 n-4부터 0까지 값에 2를 곱한 값 저장
		}
		dp[n] += 2;
		dp[n] %= bound; // 계산한 값에 나머지를 저장
		return dp[n];
	}
}

int solution(int n) {
	int answer = 0;
	answer = process(n);
	return answer;
}

다이나믹 프로그래밍 방법을 사용하여 3 x n 타일링 문제를 풀어보았습니다.