[BOJ] 2xn 타일링(11726)

[백준(BOJ)] 2xn 타일링(11726) C++

문제 : BOJ_11726번 2xn 타일링

문제 설명

DP

DP를 활용하여 해결할 수 있는 기본문제입니다.

2X1, 1X2 크기의 블록이 있고, n이 주어집니다.

이때 2Xn 크기의 직사각형을 블록을 이용해 채우는 방법의 수를 출력해야 합니다

방법의 수가 커지므로 10,007로 나눈 나머지를 출력해야 합니다.

---

Solution

n의 크기가 1이라면, 1X2 의 블록 하나를 세우는 1가지 경우의 수 밖에 없습니다.

n의 크기가 2라면, 1X2 의 블록 두 개를 세우는 경우의 수, 2X1 의 블록 두 개를 쌓는 경우의 수, 총 2개입니다.

n의 크기가 3 이상 일 때, DP를 적용할 수 있는 규칙이 있습니다.

가장 오른쪽 n 번 째 칸에 1X2 의 블록 하나를 세운다면, 그 옆에 n-1칸은 n-1개의 블록을 세워두는 경우의 수와 같습니다.

가장 오른쪽 n 번 째와 n-1 번 째 칸에 2X1 의 블록 두 개를 쌓는다면, 그 옆에 n-2칸은 n-2개의 블록을 세워두는 경우의 수와 같습니다.

그러므로 dp[n] = dp[n-1] + dp[n-2] 이 성립함을 알 수 있습니다.

---

Description

• dp의 값을 받는 배열은 vector로 동적할당하였습니다.
• resize된 vector에 값이 들어와있다면, 재귀가 들어가지 않고 return 함으로써, 메모이제이션을 했습니다.
• #define MOD 10007;로 mod 연산을 해야 할 수를 정의했습니다.

---

#include <iostream>
#include <vector>
#define MOD 10007;
using namespace std;
vector<long long> arr;
long long dp(int n);
int main(void) {
    int n;
    cin >> n;
    arr.resize(n + 1);
    cout << dp(n) << '\n';
}
long long dp(int n) {
    if (n == 1) return arr[n] = 1;
    else if (n == 2) return arr[n] = 2;
    if (arr[n] != 0) return arr[n];
    return arr[n] = (dp(n - 1) + dp(n - 2))%MOD;
}