백준 1720번 타일 코드

문제 링크입니다: https://www.acmicpc.net/problem/1720

백준 11727번 2*n 타일링 2(http://jaimemin.tistory.com/401)을 심화한 문제였습니다.

tiling 함수 구현 자체는 똑같지만 뒤집힌 경우 좌우 대칭인 경우를 찾아내는 방법을 모색하는 것이 너무 어려웠습니다.

그래서 중복되는 모양을 찾는 대신 중복되지 않는 방법을 찾았습니다.

아래는 http://m.blog.daum.net/rhaoslikesan/369?tp_nil_a=2 포스팅을 참고한 내용입니다.

tiling 함수를 통해 타일을 구하면 중복된 모양 + 중복된 모양 + 중복되지 않은 모양 이렇게 세 가지 경우의 수를 구할 수 있습니다.

현재 문제에서 요구하는 답은 (중복된 모양 + 중복되지 않은 모양) 이므로 중복된 모양을 제거하는 대신 중복되지 않은 모양을 구해서 (중복된 모양 + 중복된 모양 + 중복되지 않은 모양 + 중복되지 않은 모양)를 2로 나누면 문제에서 요구하는 답을 구할 수 있습니다!

중복되지 않은 모양은 결국 좌우가 완벽히 대칭인 모양입니다.

따라서 N이 홀수인 경우와 짝수인 경우로 나누어서 생각을 했습니다.

홀수인 경우: 가운데 밑변의 길이가 1이고 높이가 2인 직사각형을 배치하고 양 옆이 대칭인 경우 -> tiling(N/2)

짝수인 경우

1. 반으로 나누었을 때 양 옆이 대칭인 경우  -> tiling(N/2) 

2. 가운데 밑변의 길이가 1이고 높이가 2인 직사각형 두개를 배치하고 양 옆이 대칭인 경우 -> tiling((N-2)/2)

3. 밑변의 길이가 2이고 높이가 2인 정사각형 하나를 배치하고 양 옆이 대칭인 경우 -> tiling((N-2)/2)

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 30 + 1;

 

int N;

long long cache[MAX]; //타일 크기, 밑변의 길이 1 혹은 2

 

long long tiling(int width)

{

        //기저 사례: width가 1 이하일 때

        if (width <= 1)

                 return 1;

 

        long long &result = cache[width];

        if (result != -1)

                 return result;

 

        //밑변이 2인 경우(2*2, 2*1) + 밑변이 1인 경우(1*2)

        result = 2 * tiling(width - 2) + tiling(width - 1);

        return result;

}

 

int main(void)

{

        cin >> N;

 

        memset(cache, -1, sizeof(cache));

 

        int result = 0;

 

        //알고리즘: (중복 + 중복 + 중복 X + 중복 X) / 2 = 중복 + 중복 X 이므로 답

 

        //홀수이면 가운데 1*2짜리 하나가 있고 좌우 대칭 -> tiling(N/2)

        if (N % 2)

                 result = (tiling(N) + tiling(N / 2)) / 2;

        //짝수이면 가운데 1*2짜리 두개 혹은 2*2짜리 하나 넣고 좌우 대칭 -> 2 * tiling(N/2 - 1)

        //혹은 반으로 나누었을 때 양 옆이 대칭 -> tiling(N/2)

        else

                 result = (tiling(N) + (tiling(N / 2) + 2 * tiling(N / 2 - 1))) / 2;

 

        cout << result << endl;

        return 0;

}

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~