[ 프로그래머스 C++ ] 아방가르드 타일링 lv3

해설

한번 풀고싶었던 아방가르드 타일링문제.

이제 딱 보니까 어떤 식으로 풀어야 하는지 감이 온다. 완전 DP문제.

그런데 이 문제가 케이스를 6번째까지 구해야하는데 이게 완전 노가다다..

케이스를 6번까지 구해야 점화식의 식을 도출할 수 있다고 함.. 이거 완전 개싸이코적인 문제임ㅋㅋㅋㅋㅋㅋㅋㅋ

새롭게 만들수 있는 케이스와 기존에 것을 회전해서 만들 수 있는 케이스를 구분해서 만들어준다.

그런데 식이 너무너무너무 복잡해…!!!

 

정리한 식은 다음과 같다.

F(n) = F(n-1) + F(n-2)*2 + F(n-3)*5 + Sum(n-4)*2 + Sum(n-5)*2 + Sum(n-6)*4

이렇게 되는 이유는 만약 7 이상부터는 7을 만들고자 하면 3*1(직선) 타일이 중간에 들어가서 새로운 모양의 타일을 만들 수 있게된다. 8도 그렇고 9도 마찬가지이다. 이를 4+3k, 5+3k, 6+3k 로 표시할 수 있다. 따라서 정리하기 전의 식은 원래 아래와 같이 되는것.

F(n) = F(n - 1) + F(n - 2) * 2 + F(n - 3) * 5 + sum(F(n - 4 - 3k)) * 2 + sum(F(n - 5 - 3k)) * 2 + sum(F(n - 6 -3k)) * 4

 

규칙을 찾아내는게 어려운 문제다. 풀이자체는 어렵지 않은데 규칙이 아주 까다로웠다... 규칙도 질문하기 란에 있는 힌트를 보고나서야 얻었다.

---

문제 설명

정우는 예술적 감각이 뛰어난 타일공입니다. 그는 단순한 타일을 활용하여 불규칙하면서도 화려하게 타일링을 하곤 합니다.

어느 날 정우는 가로 길이 n, 세로 길이 3 인 판을 타일링하는 의뢰를 맡았습니다. 아방가르드한 디자인 영감이 떠오른 정우는 다음과 같은 두 가지 종류의 타일로 타일링을 하기로 결정했습니다.

각 타일은 90도씩 회전할 수 있으며 타일의 개수는 제한이 없습니다.

n이 주어졌을 때, 이 두 가지 종류의 타일로 n x 3 크기의 판을 타일링하는 방법의 수를 return 하도록 solution 함수를 완성해주세요.

---

코드

#include <string>
#include <vector>

long long dp[100002] = { 1, 1, 3, 10, 23, 62, 170, };
long long sum[100002] = { 1, 1, 3, 11, 24, 65, 181, };
using namespace std;

const int Div = 1e9+7;

int solution(int n) {
    int answer = 0;
    
    for(int i=7; i<=n; i++)
    {
	dp[i] = dp[i - 1] + dp[i - 2] * 2 + dp[i - 3] * 5;
	dp[i] += sum[i - 4] * 2 + sum[i - 5] * 2 + sum[i - 6] * 4;
	dp[i] %= Div;

	sum[i] = dp[i] + sum[i - 3];
	sum[i] %= Div;
    }
    
    return dp[n];
}