[C++] 백준 11726 2×n 타일링

11726 2×n 타일링

11726번: 2×n 타일링

C++

#include <iostream>
#include <vector>

using namespace std;

vector<int> DP(1003);

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    DP[1] = 1; DP[2] = 2;

    for(int i= 3; i<=n; i++)
        DP[i] = (DP[i-1] + DP[i-2])%10007;
    cout << DP[n] << '\n';

    return 0;
}

 

다이나믹 프로그래밍을 이용한 문제이다. 2 x 1일 때 방법의 수가 1, 2 x 2일 때 방법의 수가 2이라는 것은 쉽게 구할 수 있으며, DP를 진행하기 전에 초기화시켜준다.

재귀로 구현한 DP보다 반복분 형식으로 구현한 DP가 훨씬 효율적이다.

DP 배열에 memoization(메모이제이션)을 이용해 타일링의 경우의 수를 저장해둔다.

 

modulo 연산의 속성에 따라 매번 나머지 연산을 해 주어도 결괏값은 동일하게 된다.

모듈러 연산에 있어서는 추후 게시물을 통해 다룰 예정.