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

문제

https://www.acmicpc.net/problem/11726
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 출력하는 문제다.

---

풀이

길이 n에서 세로 타일을 사용하면 길이가 1 줄고, 가로 타일을 사용하면 길이가 2 줄어든다.

Top-down vs Bottom-up

Top-down(재귀 호출)
: 가장 큰 문제를 방문 후 작은 문제를 호출 하여 답을 찾는 방식
-> 점화식을 이해하기 쉽다.

Bottom-up(반복문)
: 가장 작은 문제들 부터 답을 구해가며 전체 문제의 답을 찾는 방식
-> 함수를 재귀 호출하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다.

---

Top-down

go(int c, int r, int rest)
c = 세로 사용 개수, r = 가로 사용 개수, rest = 남은 길이

dp[c][r]
dp에는 c, r을 저장했다.

#include <iostream>
using namespace std;
int n, dp[1001][1001];

int go(int c, int r, int rest)
{
    if (rest == 0 || rest == 1)
        return 1;
    if (dp[c][r])
        return dp[c][r] % 10007;

    dp[c][r] += go(c + 1, r, rest - 1);
    dp[c][r] += go(c, r + 1, rest - 2);

    return dp[c][r] % 10007;
}

int main()
{
    cin >> n;
    cout << go(0, 0, n) << "\n";
}

정답처리 됐지만 소요 시간이 8ms 이라서 Bottom-up 방식으로 다시 풀었다.

---

Bottom-up

생각해보면 dp[현재 길이]는
현재 길이에서 1을 뺀 dp에서 세로 1개를 더하거나
현재 길이에서 2를 뺀 dp에서 가로 1개를 더하는 경우의 수가 있다.
이걸 이용해서 점화식을 세울 수 있다.

dp[n] = dp[n-1] + dp[n-2]

---

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, dp[1001];
int main()
{
    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";
}