프로그래머스: 3*N 타일링 [C++]

https://school.programmers.co.kr/learn/courses/30/lessons/12902

프로그래머스

 

문제

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

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

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

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

 

제한사항

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

 

입출력 예

n	result
4	11

 

 

흠냐

일단 문제를 보고 제일 처음 든 생각은 n이 홀수면 안되는거지... (1은 되것지만)

수학문제인데 식을 어떻게 세울 것인지

음... 저렴한 그림

무튼 길이가 늘어날 때마다 저런 특수한 경우가 2개씩 생기고, 이전 경우의 특수 경우까지 고려해야 함에 주의해야 한다

 

#include <string>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int solution(int n) {
	if (n % 2 != 0) return 0;
	long long dp[5001] = { 0, };
	dp[0] = 1;
	dp[2] = 3;
	for (int i = 4; i <= n; i += 2) {
		dp[i] = dp[i - 2] * 3;
		for (int j = i - 4; j >= 0; j -= 2) {
			dp[i] += dp[j] * 2;
		}
		dp[i] %= MOD;
	}
	return dp[n];
}

dp[0]은 사실 0이 아니라 1일 경우에 대한 이야기지만... 예외니까 계산하기 편하라고 그냥 0으로

ㅜ 이해가 어려웟음