[BOJ 백준] 11727번 : 2xn 타일링 2 (C++)

[BOJ 백준] 11727번 : 2xn 타일링 2 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

https://www.acmicpc.net/problem/11727

 

문제

 

입력

 

출력

 

예시

 

---

02. 접근 방식

 

요약

1. 2*n이라고 가정할 때, x(1≤x ≤n) 번째에 도달할 수 있는 경우를 생각

1) x-2번째에서 2*2의 정사각형을 1개 배치

2) x-2번째에서 1*2(세로)의 직사각형을 2개 배치

3) x-1번째에서 2*1(가로)의 직사각형을 1개 배치

2. 점화식 f(n) = f(n-1) + 2*f(n-2) 성립

 

과정

요약에 적힌 내용이 곧 과정이어서, 추가로 작성할 내용이 없습니다..

 

주의점

1. 초기값 설정에 대해 유의해야 합니다.

f(0) = 1로 설정합니다.

1번째에 도달할 수 있는 경우를 보면, f(1) = f(0) + 2*f(-1)입니다.

f(-1)은 존재할 수 없으므로, f(1)도 1로 처리합니다.

 

따라서, f(0) = f(1) = 1로 설정하고, f(2)부터 검사를 진행하면 됩니다.

 

2. 모듈러의 나머지 정리를 이용해, 매 번 계산할 때마다 10'007의 수로 나눠도 무방합니다.

 

추가

만약에 메모리 공간 낭비를 더 줄이고자 한다면, 배열 3칸만 사용해서 해결할 수 있습니다.

계산할 때마다 데이터를 앞으로 한 칸씩 옮기면, 가능합니다.

예를 들어서 배열 a에 int형 데이터를 3칸 넣을 수 있다고 가정합니다.

a[0] = f(1), a[1] = f(2)이고 a[2]에 f(3)에 대한 결괏값을 대입합니다.

그 후, a[0] = f(2), a[1] = f(3)으로 데이터를 한 칸씩 옮기고 a[2]에는 f(4)에 대한 결괏값을 대입합니다.

위 과정을 반복하면, 3칸의 배열로도 f(n)에 대한 결과값을 얻을 수 있습니다.

 

---

03. 정답 코드

// 실버 3 - 11727번 : 2×n 타일링 2
// 작성자 : free4760(jeonghoe22)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// f(n)
// 1. 1*2칸 채우기 : f(n-1)
// 2. 2*1칸 채우기 : f(n-2)
// 3. 2*2칸 채우기 : f(n-2)
// f(n) = f(n-1) + 2f(n-2)

int MOD = 10007;

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 입력
    int n;
    cin >> n;

    // 할당
    vector<int> cases(max(n+1, 3), 0);
    cases[1] = 1;
    cases[2] = cases[1] + 2;

    // 계산
    for(int i = 3; i <= n; i++)
    {
        cases[i] = (cases[i-1] + 2 * cases[i-2]) % MOD;
    }

    cout << cases[n] << "\n";
}

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!