#[プログラマー][練習問題]3 xN平舗解題

クイズクリップ

👓 問題の概要
有名なDP問題2 xNタイルのアップグレードバージョン
今立てている長さは2ではなく3!!
DP公式を導き出せば簡単に解ける!!
問題の詳細と制限については、Programmersのホームページを参照してください.問題に答える
🔑 問題を解く
dp式を導くには、順番に描いておけばわかります.
nが奇数であれば、タイリングはできないので、答えは0です.
絵を描くと.

n:2の場合、答えは3

n:3の場合、答えは0

n:4の場合、答えは11です.

n:6の場合、答えは41です.(描きすぎたので探しました)

n:8の場合、答えは153です.(描きすぎたので探しました)

nが4の時だと思います.

3 X 2タイリング方法の数*3 X 2タイリング方法の数=9

nは4時のみ作成できるメソッド2を合わせて11種類ある.
(ㅣㅣ=このように中央横タイルを置く)

nが6の時だと思います.

3 X 4タイリング方法の数*3 X 2タイリング方法の数=33
(3 X 4には、3 X 2と3 X 2で作成できるすべてのケースの数が含まれています.)

nが6の場合に作成できるタイル数2

さらに考慮すべきは、3×2のタイルの工数*2と3×4で作られるタイルに、2種類を乗じたものである.=6
3 X 4タイルの方法の数*3 X 2タイルの方法の数の場合、右側の4格子を含む3 X 4のみで作成できる2つの場合の数は含まれません.

nが8の場合

上記のように、3 X 6時のタイリング方法数*3 X 2時のタイリング方法数=123

n作成できるのは8時のみ:2

3 X 2の場合、タイルメソッド数*3 X 6の場合のみ作成できるタイル数=6

3 X 4の場合、タイルメソッド数*3 X 4の場合のみ作成できるタイル数=22

感じましたか?3 XNをタイリングする場合、

3 X(n-2)*3 X 2に

を乗じる

nの場合のみ2つの

を作成できます.

3 X 2*(3 X(n-2)の場合のみ作成)

3 X 4*(3 X(n-4)の場合のみ2つ作成可能)...前の数字は3倍速(n-2)に等しい.

言い換えれば

N-2時の数字*3(3 X 2タイリング方法の数)

Nの場合のみ2つの

を作成できます.

N-2k(k = 1,2,3....) N−2 kがN−2である前の数に2を乗せればよい.

🥽 ソースコードとソースコード分析
プログラマサイトではなく、Visual Studioによって作成されたコードがインポートされます.いくつかのテストコードがあります.

#include <string>
#include <vector>

using namespace std;

//풀이
//ex n = 8
//더해야할 것
//answer(6) * answer(2)
//answer(2) * 2 (n 이 6일때만 존재하는 2개의 경우)
//answer(4) * 2 (n 이 4일때만 존재하는 2개의 경우)

//dp1의 인덱스는0 부터 시작되며 n이 2씩 증가할 때 마다의 값이 저장됨 n이 2,4,6,8 ....일 때
//dp2는 인덱스 0 부터 인덱스 n - 2 까지의 각각의 값 *2 의 합이 저장.

long long dp1[4096];
long long dp2[4096];
int solution(int n);
int main() {
    solution(16);
}
int solution(int n) {
    if (n % 2 == 1)
        return 0;
    dp1[0] = 3;
    dp1[1] = 11;
    dp2[1] = 6;
    for (int i = 2; i < n / 2; i++) {
        dp1[i] = (dp1[i - 1] * 3 + dp2[i - 1] + 2) % 1000000007;
        dp2[i] = (dp1[i - 1] * 2 + dp2[i - 1]) % 1000000007;
    }
    return dp1[n / 2 - 1];
}

🔨 問題ポスト
デジカメは難しいです.簡単な問題ほど難しい.
考えすぎて、時間がかかる問題も思ったより多いです.
がんばってください.