[BOJ] 11727 2×n 타일링 2

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

11727번: 2×n 타일링 2

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

 

dynamic programming

 

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

 

타일의 가로 길이에 대해서만 생각한다.

가로 길이 n을 1과 2(1), 2(2)를 더해서 만드는 방법의 수를 세면 된다.

즉, 길이는 2이지만 (1)과 (2)라는 서로 다른 수가 존재한다고 가정한다.

 

n = 1+(n-1)

   = 2(1)+(n-2)

   = 2(2)+(n-2)

이런 방식으로 n을 나눌 수 있다.

 

이걸 식으로 표현하면

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

이 때, 2(1)과 2(2)의 경우의 수 차이가 없으므로 nums[n] = nums[n-1] + nums[n-2]*2로 표현할 수 있다.

이 점화식을 사용해 nums[n]을 구해준다.

#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;

// nums[i] = i를 만드는 방법의 가짓수
int nums[1001] = {0, };

int solution(int n){
    if(nums[n] > 0){
        return nums[n];
    }
    return nums[n] = (solution(n-1) + solution(n-2) * 2)
                        % 10'007; // 2를 만드는 방법이 2가지이므로 x2
}

// 1,2(1),2(2)를 더해 n을 만들기
int main(void){
    FASTIO;
    int N;
    cin >> N;
    nums[1] = 1; nums[2] = 3;
    cout << solution(N) << "\n";
    return 0;
}

 

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

 

이전 2xn 타일링 문제와 달라진 점은 2를 만드는 방법이 2가지가 되었다는 것인데,

그 부분은 해결할 방법이 쉽게 떠올랐다.

다만, 며칠 됐다고 이전 방법이 바로 떠오르지 않은게 충격..

떠오르지 않았는데도 바로 방법을 잘 찾았으니 다행인 것일까?