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

❓ 문제

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

🎯 난이도

Silver ⚪3

🧠 풀이

1. 내 풀이 (DP)

- 알고리즘

• Dynamic Programming

- 설명

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

언뜻 보면 어떤 규칙이 있을까 싶지만, 확실한 규칙이 존재한다. 사각형의 맨 오른쪽은 무조건 '|', '=' 모양으로 끝나게 된다.

따라서 이에 따라 점화식을 만들어 주면 다음과 같다.

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

참고로 이 점화식에 따르면 피보나치 수열과 같은 양상을 띠게 되는데, 이 문제의 조건인 1000번째까지 가게 되면 엄청나게 커지므로 꼭 반복문의 모든 계산에 모듈러 연산을 해주는 것을 잊지 말자.

반복문 하나로 모든 연산이 끝나므로, 시간 복잡도는 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] = 2;

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

    cout << vecDP[iN];

    return 0;
}

---

💭 후기

처음엔 어떻게 풀어야하나 고민됐지만, 앞의 결과들을 다음 n에서도 쓸 수 있다는 것을 생각하고, 점화식을 세울 수 있지 않을까 싶었다. 이러한 경우의 수 문제일 경우에 식을 세울 수 있을지를 잘 생각해보자.

🔗 참고자료

• 동적 계획법