[알고스팟/ALGOSPOT] 18. ASYMTILING

이번 문제는 ASYMTILING 라는 문제입니다!! 이 문제는 전의 TILING2의 문제와 굉장히 유사합니다.

ASYMTILING(출처 : https://algospot.com/judge/problem/read/ASYMTILING)

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • ASYMTILING
  • 1000ms
  • 65536kb
  • 1099
  • 570 (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

노트

이전의 TILING2 문제와 굉장히 유사하지만 고려해야 되는 부분이 있습니다. 

이 문제에서는 TILING2의 경우의 수 가운데 대칭이 되는 TILING은 제외를 해야됩니다. 

하지만 동적계획법을 하면서 모든 경우를 따지기는 어수선함으로

TILING2의 경우의 수를 구하고 거기서 대칭의 경우의 수를 제거하는 방향으로 해결합니다.

TILING2의 점화식은 이전 게시물 ( TILING2 )에서 처럼

TILING(POINT) = TILING(POINT - 1) + TILING(POINT - 2)가 됩니다. 

여기서 이제 대칭 TILING을 제거하면 되는데 

대칭 TILING은 반을 기준으로 왼쪽과 오른쪽이 같으므로 TILING의 동적계획법을 반만큼 돌려서 해결합니다. 

하지만 고려해야할 부분은 가운에데 -가 되는 경우도 가능하므로 POINT > N을 넘어가는 부분에서 0을 반환했던거와는 달리

1을 반환하여 해결합니다. 

#include <iostream>

using namespace std;

 

void INPUT(); // 입력 함수

long long int SOLVE(int point); // TILING2를 구하는 함수

long long int ASYMTILING(int point); // 대칭 TILING을 구하는 함수

long long int cache[110]; // 메모이제이션 배열

int N, mid; 

int main()

{

int testcase;

scanf("%d", &testcase);

while(testcase >= 1)

{

--testcase;

INPUT();

}

return 0;

}

void INPUT()

{

long long int TILING, out;

scanf("%d", &N); // N을 입력 받는다.

for(int i=0; i<=N; i++) cache[i] = -1; // 메모이제이션을 -1(초기화값)로 초기화한다.

TILING = SOLVE(0); // TILING2의 경우의 수를 구한다. 

for(int i=0; i<=N; i++) cache[i] = -1; // 다시 배열을 초기화

if(N % 2) mid = N / 2 + 1; // 가운데 인덱스 값을 구한다.

else mid = N / 2; // 가운데 인덱스 값을 구한다.

out = TILING-ASYMTILING(0); // TILING2의 경우의 수에서 대칭TILING의 경우의 수를 빼준다.

if(out < 0) out += 1000000007; // 음수 처리

printf("%d\n", out);

}

long long int SOLVE(int point) // TILING2 이전과 똑같다.

{

long long int &ret = cache[point]; // 기억해둔 값을 가져온다.

if(ret != -1) return ret; // 기억해둔 값이 있으면 반환

if(point > N) return 0; // 넘어가면 안된다.

else if(point == N) return 1; // 같으면 1 반환

ret = SOLVE(point + 1) + SOLVE(point + 2); // 점화식

if(ret > 1000000007) ret %= 1000000007;

return ret;

}

long long int ASYMTILING(int point) // 대칭 TILING

{

long long int &ret = cache[point]; // 기억해둔 값을 가져온다.

if(ret != -1) return ret; // 기억해둔 값이 있다면 반환.

if(point >= mid) return 1; // POINT > N인 경우는 중간지점에서 -을 놓은 경우이므로 1 반환

ret = ASYMTILING(point + 1) + ASYMTILING(point + 2); // 점화식

if(ret > 1000000007) ret %= 1000000007;

return ret;

}