[BaekJoon 11727][⚪3] 2×n 타일링 2

❓ 문제

백준 11727 - “2×n 타일링 2”

🎯 난이도

Silver ⚪3

🧠 풀이

1. 내 풀이 (DP)

- 알고리즘

• Dynamic Programming

- 설명

DP 알고리즘을 활용한 풀이이다.

이 문제는 2×n 타일링 문제의 후속 문제로, 한 가지 규칙을 더 추가한 문제이다. 원래는 사각형의 맨 오른쪽이 무조건 '|', '=' 모양으로 끝나는데, 이에 'ㅁ'모양까지 추가되는 것이다.

이를 점화식으로 만들려면, 원래의 = 모양의 식이 dp[i - 2]이고 이는 ㅁ와 같은 식이므로 2 * dp[i - 2]로 바꿔주기만 하면 끝이다. 따라서 점화식은 다음과 같다.

\[dp[i] = dp[i - 1] + 2 * dp[i - 2]\]

이 문제 또한 DP의 값이 갈수록 굉장히 커지므로, 꼭 반복문의 모든 계산에 모듈러 연산을 해주는 것을 잊지 말자.

반복문 하나로 모든 연산이 끝나므로, 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <vector>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    // DP 배열
    vector<int> vecDP(iN + 1);
    // 초기값 저장
    vecDP[1] = 1;
    vecDP[2] = 3;

    for(int i = 3; i <= iN; ++i)
    {
        // 오버플로우 방지 위해 항상 모듈러 계산
        vecDP[i] = (vecDP[i - 1] + 2 * vecDP[i - 2]) % 10007;
    }

    cout << vecDP[iN];

    return 0;
}

---

💭 후기

2×n 타일링 문제의 후속 문제로, 하나의 규칙만 더 추가하면 되므로 그리 어렵지 않게 풀 수 있다. 이러한 규칙들을 점화식으로 치환하는 연습을 열심히 하자.

🔗 참고자료

• 동적 계획법