[Baekjoon Online Judge] 백준 11727번 2×n 타일링 2(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 11727번 2×n 타일링 2

(C++, Python)

(글쓴날 : 2020.04.14)

 

---

* Baekjoon Online Judge, 백준 11727번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 11727번 2×n 타일링 2

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

1이상 1000이하의 n이 주어지고, 2 X n 크기의 직사각형을 1 X 2, 2 X 1, 2 X 2 타일로 채우는 방법의 수를 10007로 나눈 나머지를 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였으며, C++과 Python을 사용했습니다.

점화식을 세우기 위한 규칙은 타일을 직접 그려나가다 보면 감이 오는데, n이 3일 때부터 규칙을 찾을 수 있습니다.

사실, 이전 시리즈 문제인 2×n 타일링과 다를 바 없으며(이 문제는 2×n 타일링2입니다.) 만약, 풀지 않으셨다면 이전 문제를 먼저 푸신 뒤, 다시 이 문제를 푸시는 게 나을 것 같습니다.

n이 3일 때 타일을 채우는 경우는 n이 2인 경우에 1 X 2 타일을 이어 붙인 경우와, n이 1인 경우에 2 X 1 혹은 2 X 2 타일을 이어 붙인 경우의 합이며, 이 규칙은 이후에도 쭉 유지됨을 알 수 있습니다.

따라서, n이 1과 2인 경우엔 각각 1가지, 3가지의 경우 밖에 나올 수 없으므로 반복문에서 예외 처리를 해준 후 3부터는 세운 점화식을 통해 memoization하여 문제를 해결했습니다.

 

단, 주의해야 할 부분이 있는데 Python의 경우 정수 입력 범위의 제한이 없어서 모든 연산이 끝난 후 마지막 결과에 10007을 나눈 값을 출력하면 되지만, C++의 경우 memoization할 때 연산 결과마다 미리 10007로 나눠주지 않으면 어느 순간 int형의 최대 범위를 초과하게 됩니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    cin >> n;
 
    vector<int> memoization(n, 0);
 
    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            memoization[0] = 1;
            continue;
        }
        if (i == 1)
        {
            memoization[1] = 3;
            continue;
        }
 
        memoization[i] = (memoization[i - 1] + (memoization[i - 2]) * 2) % 10007;
    }
 
    cout << memoization[n - 1];
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
n = int(input())
memoization = [0] * n
 
for i in range(n):
    if i == 0:
        memoization[0] = 1
        continue
    if i == 1:
        memoization[1] = 3
        continue
    
    memoization[i] = memoization[i - 1] + (memoization[i - 2] * 2)
 
print(memoization[-1] % 10007)

---