[C++] 문제해결기법 과제 3: 칸 채우기

 

3 x n 크기의 네모칸이 있다. 이 칸을 3 x 1 크기의 블럭을 이용하여 겹치지 않고 빼꼭하게 채우는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오. 이 문제를 푸는 .c/.cpp/.java 파일 하나를 제출하시오.

 

예를 들어, n = 1일때는 1가지, n = 2일 때는 1가지, n = 3일 때는 2가지임을 쉽게 알 수 있다. n=3인 경우를 세 블럭 OOO, XXX, MMM으로 채운 두 가지 경우가 아래 그림과 같다.  

OXM    OOO

OXM    XXX

OXM    MMM

 

입력 

표준 입력으로 받는다. n을 나타내는 정수 하나가 주어진다. n은 1 이상 45 이하이다. 

 

출력 

표준 출력으로 한 줄에 정수 하나를 출력한다. 이 정수는 문제의 조건을 만족하는 가짓수를 나타낸다.

 

예제 입력 1

1

예제 출력 1

1

예제 입력 2

3

예제 출력 2

2

예제 입력 3

4

예제 출력 3

3

 

#include <iostream>
using namespace std;
 
// 45 넣어서 조합 계산할때 permutation 값이 2,147,483,647 넘어가기 때문에 long long 으로 설정함.
long long Combination(int n, int r)  // nCr = nPr / r!
{
    long long p = 1, f = 1, c = 1;
    for (int i = n; i > n - r; i--) { p = p * i; }
    if (r) {
        for (int i = r; i > 0; i--) { f = f * i; }
        c = p / f;
    }
    else c = 1;  // nC0
    return c;
}
 
long long countWays(int n)
{
    long long ways = 0;
    int tbyt = n / 3;
    if (tbyt) {
        for (int i = 0; i <= tbyt; i++) {
            ways += Combination(n - 2 * i, i);
        }  // n-3t+t = n-2t
    }
    else if (!tbyt) ways = 1;
    return ways;
}
 
int main()
{
    int n = 1;  // n은 1 이상 45 이하
    cin >> n;
    cout << countWays(n);
    return 0;
}

 

https://www.geeksforgeeks.org/tiling-with-dominoes/?ref=rp

Tiling with Dominoes - GeeksforGeeks

 

점수 10/10