[BOJ] 11726 2xn 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

dp

 

---------------------------------------------------풀이----------------------------------------------------

 

사각형의 가로만 생각했을 때, n을 1이나 2를 더해 만드는 가짓수와 같다.

이 가짓수를 dp[] 배열에 구할 때마다 저장해 리턴할 수 있도록 한다.

dp[n] = dp[n-1] + dp[n-2] 이다.

즉, n=1+(n-1) 이거나 n=2+(n-2)이다.

이때, 초기값으로 dp[1] = 1, dp[2] = 2를 저장해두었다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

// 방법의 가짓수
int dp[1001] = {0, };

int solution(int n){
    if(dp[n] > 0){
        return dp[n];
    }
    return dp[n] = (solution(n-1) + solution(n-2)) % 10007;
}

// 사각형의 가로 길이만 생각
// 1이나 2를 더해 n을 만드는 경우의 수=?
int main(void){
    FASTIO;
    int N;
    cin >> N;
    dp[1] = 1;
    dp[2] = 2;
    cout << solution(N) << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

간단한 dp문제.

이전에 1,2,3을 더해 만드는 문제를 풀었는데 그보다 쉬운 버전이다.