[알고스팟] 비대칭 타일링

문제링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • ASYMTILING
  • 1000ms
  • 65536kb
  • 2850
  • 1466 (51%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 좌우 대칭이어서는 안 됩니다. 위 그림은 2 * 5 크기의 직사각형을 채우는 비대칭 타일링 방법 6가지를 보여줍니다. 다음의 2가지는 좌우대칭이기 때문에 세지 않습니다.

n 이 주어질 때 가능한 비대칭 타일링 방법의 수를 계산하는 프로그램을 작성하세요. 방법의 수는 매우 클 수 있으므로, 1,000,000,007 로 나눈 나머지를 출력합니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 그 후 각 줄에 사각형의 너비 n (1 <= n <= 100) 이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지를 출력합니다.

예제 입력

3
2
4
92

예제 출력

0
2
913227494

어떻게 풀까?

이전에 나왔던 타일링을 세는 문제와 매우 유사한 문제입니다.

이번에는 비대칭만을 세야하는 문제인데 어떻게 해결하면 좋을까요?

하나의 모형이 있다고 합시다. 그렇다면, 이 모형은 다음 2가지 중에 하나일 것입니다.

1. 대칭.

2. 비대칭.

생각보다 간단하지만, 이 문제의 해결 방법은 여기서부터 시작됩니다.

생각보다 대칭을 세는 것이 매우 쉽기 때문에, 비대칭의 개수는

전체의 개수 - 대칭의 개수 를 구하면 됩니다!!

그렇다면 대칭의 개수를 구하는 방법을 알아봅시다!!!

대칭인 경우는 크게 3가지 경우로 나눌 수 있습니다.

맨 위의 경우는 N이 홀수일 경우입니다. 이 경우에는 가운데에 무조건 세로 막대가 하나 있어야 합니다.

아래 2가지 경우에는 N이 짝수일 경우입니다.

파란색을 끼워 넣으면, 이제 나머지 회색 사각형의 부분이 똑같아야 대칭이 되는 것입니다.

그렇다면, 회색 부분에 만들 수 있는 비대칭 타일의 개수는 몇개일까요?

너비가 N이라고 했을 때 비대칭 타일의 수를 비대칭(N)이라고 한다면,

N이 홀수일 경우에는 비대칭((N-1)/2)개이고, 

N이 짝수일 경우에는 비대칭(N/2 - 1) + 비대칭(N/2)개 일 것입니다.

이제 이를 통해 코드를 작성해 봅시다!

코드

#pragma once
#include<cstdio>
 
int fibo[101] = { 1, 1 };
int sync[101] = {1, 1};
 
const int INF = 1000000007;
 
int main()
{
    int t;
 
    for (int i = 2; i <= 100; i++)
    {
        fibo[i] = (fibo[i - 1] + fibo[i - 2]) % INF;
        sync[i] = i & 1 ? fibo[(i - 1) / 2] : (fibo[i/2] + fibo[i/2 - 1]) % INF;
    }
 
    scanf("%d\n", &t);
 
    while (t--)
    {
        int n;
        scanf("%d\n", &n);
 
        printf("%d\n", (INF + fibo[n] - sync[n])%INF);
    }
    return 0;
}
 

여담

결과를 출력할 때 INF를 더했다가 출력하는 것에 주목합시다!

이는 fibo와 sync에는 나머지값이 들어있기 때문입니다.

따라서, 오버플로우 때문에 fibo[n]값이 sync[n]값보다 작을 수도 있습니다.

따라서, fibo[n] - sync[n] 값이 음수로 나올수도 있습니다!

하지만 계산 방식을 저렇게 해 두면, 이제 0보다 작은 값이 나오는 것을 방지할 수 있습니다.