[boj](s 3)117262 xnタイル


✅ DP ✅ Bottom up ✅ Top down

質問する


リンク


に答える


1.問題のアクセスと解決ロジック(解法)


2×n矩形の第3の充填矩形の方法は2つある.
1.縦タイル(2 x 1)を1つ置く.
2.2つの横タイル(1 x 2)を配置します.
したがって、第3の充填方法の数
2∮(iタイルを充填する方法の数)2*(iタイルを充填する方法の数)2∮(iタイルを充填する方法の数).
定義

  • f(i)=2∗(iタイルを充填する方法数)f(i)=2*(iタイルを充填する方法数)f(i)=2∗(iタイルを充填する方法数)2479182
  • の答え
    f(n)f(n)f(n)
  • 初期値
    f(0)=1,f(1)=2f(0)=1, f(1)=2f(0)=1,f(1)=2
  • 点火式
    f(i)=f(i−1)+f(i−2),(i>2)f(i)=f(i-1)+f(i-2),(i>2)f(i)=f(i−1)+f(i−2),(i>2)

  • 初期値
    0番目:垂直タイルが1つしかありません.
    1つ目:縦2つまたは横2つのタイルがある場合があります

  • てんかしき
    3番目に配置するブロックは、i-1 i-1 i-1およびi-2 i-2 i-2番目に配置するブロックが何であるかによって異なります.
  • たとえば、(i-2)(i-2)(i-2)->(i-1)(i-1)(i-1)->(i)(i)(i)の順にブロックを配置します.

  • i,2 i−2 i,2に横ブロックを置くと、横ブロックの横寸法が2になるので、i,1 i−1 i,1に同じ横ブロックを置くこともでき、iiiには縦ブロックのみを置くことができる.(自動決定)

  • i,2 i−2 i,2に縦隊が置かれている場合,i,1 i−1 i,1における縦隊も横隊も可能であり,iiiはi,1 i−1 i,1にどの隊が置かれているかによって自動的に決定される.
  • 従って、点火式は、f(i)=f(i)+f(i),(i>2)f(i)=f(i-1)+f(i>2),(i>2)f(i)=f(iέ1)+f(i>2),(i>2)

    2.コード


    -Bootom Up(繰り返し文、星雲)

    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    
    
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    
        int n;
        cin >> n;
        
        int block[n];
        block[0] = 1;
        block[1] = 2;
        
        for(int i = 2; i<n ; i++){
            block[i] = (block[i - 1] + block[i - 2]) % 10007;
        }
        
        cout << block[n-1] << "\n";
    
        return 0;
    }

    🔥 メモリオーバーフロー


    初めてやったから
    block[i] = (block[i - 1] + block[i - 2])
    ブロックに直接数字を挿入して解くと、例のように正解は正しいがbackjuneでは間違っている.恐らくこれ以降になると、状況が多くなり、メモリの問題が発生する可能性があります.
    問題の出力値で10007で割った余剰値を求めるので、blockでは、10007で割った余剰値に数を乗じて計算しても、点火式は同じなので問題は解決できます.

    -上部Down(再帰、コメント作成)

    #include <iostream>
    #include <algorithm>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    int n;
    int block[1001];
    
    int cal(int n){
        if(n==0) return 1;
        if(n==1) return 2;
        
        if(block[n] != 0) return block[n]; // 이미 센것은 넘어감 (메모이제이션)
        
        block[n] = (cal(n-1) + cal(n-2)) % 10007; // 메모이제이션
        return block[n];
    }
    
    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    
    
        cin >> n;
     
        block[0] = 1;
        block[1] = 2;
    
        cal(n-1);
    
        cout << block[n-1] << "\n";
    
        return 0;
    }

    🔥 タイムアウト


    再帰関数で求めた値(現在)を保存し、同じn番目の場合に同じ数を使用する必要がある場合は、同じ演算(以前に求めて保存したのでスキップ)を行う必要がなく、タイムアウトを回避

    3.時間複雑度分析


    3つ目の場合、すべての数字が得られます.
    O(N)O(N)O(N)

    4.問題の重要な部分


    DP問題で重要なのは,点火式の導出である.
    オプションはBootm Up(繰り返し文)で展開するか、Top Down(再帰)で展開するか