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

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

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

(C++, Python)

(글쓴날 : 2020.04.14)

 

---

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

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

---

 

 

백준 11726번 2×n 타일링

---

1) 문제

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

11726번: 2×n 타일링

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

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

 

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

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

n이 3일 때 타일을 채우는 경우는 n이 2인 경우에 1 X 2 타일을 이어 붙인 경우와, n이 1인 경우에 2 X 1 타일을 이어 붙인 경우의 합이며, 이 규칙은 이후에도 유지되고 마치 피보나치 수열과 비슷함을 알 수 있습니다.

따라서, n이 1과 2인 경우엔 각각 1가지, 2가지의 경우 밖에 나올 수 없으므로 반복문에서 예외 처리를 해준 후 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] = 2;
            continue;
        }
 
        memoization[i] = (memoization[i - 1] + memoization[i - 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] = 2
        continue
 
    memoization[i] = memoization[i - 1] + memoization[i - 2]
    
print(memoization[-1] % 10007)

---