비대칭 타일링 문제 질문입니다!

  • universalee
    universalee

    제가 생각한 것이 맞는지 궁금해서 질문드립니다.
    일단 비대칭 타일링 방법의 수를 구하기 위해서
    (전체 타일링 방법의 수)-(대칭인 타일링 방법의 수)라고 생각했고,
    이를 토대로 계산한 결과,
    전체 타일링 방법의 수 f(n)
    대칭인 타일링 방법의 수 g(n)
    f(n) = n (단, n<=2일 때)
    f(n-2)+f(n-1) (단, n>2일 때)

    g(n): n=1일 때 g(1)=1
    n=2일 때 g(2)=2
    n=3일 때 g(3)=1
    m>=1일때 g(2m+3) = g(2m+1)+g(2m-1)

    g(2m+2) = g(2m)+g(2m+1)

    비대칭 타일링 방법의 수 h(n) = f(n) - g(n)
    이라는 공식을 유도해내서 이를 바탕으로 전체 타일링 방법의 수를 구하는 함수, 대칭인 타일링 방법의 수를 구하는 함수, 비대칭인 타일링 방법의 수를 구하는 함수를 만들었습니다.

    unsigned long long NumOfWay[101];
    unsigned long long NumOfSym[101];
    unsigned long long Tiling(int n);
    unsigned long long Symmetry(int n);
    unsigned long long Asymtiling(int n);
    
    unsigned long long Tiling(int n){
        memset(NumOfWay, 0, sizeof(unsigned long long) * 101);
        int size = sizeof(NumOfWay) / sizeof(NumOfWay[0]);
        for (int i = 1; i < size; i++){
            if (i == 1 || i == 2){
                NumOfWay[i] = i;
            }
            else{
                NumOfWay[i] = NumOfWay[i - 2] + NumOfWay[i - 1];
            }
        }
        return NumOfWay[n];
    }
    
    unsigned long long Symmetry(int n){
        memset(NumOfSym, 0, sizeof(unsigned long long) * 101);
        int size = sizeof(NumOfSym) / sizeof(NumOfSym[0]);
        for (int i = 1; i < size; i++){
            if (i == 1 || i == 2){
                NumOfSym[i] = i;
            }
            if (i == 3){
                NumOfSym[i] = 1;
            }
            if (i > 3 && i % 2 != 0){
                NumOfSym[i] = NumOfSym[i - 4] + NumOfSym[i - 2];
            }
            if (i > 2 && i % 2 == 0){
                NumOfSym[i] = NumOfSym[i - 2] + NumOfSym[i - 1];
            }
        }
        return NumOfSym[n];
    }
    
    unsigned long long Asymtiling(int n){
        return Tiling(n) - Symmetry(n);
    }
    

    제가 생각한 방법이 맞는지요? 92의 출력결과는 답과 상이한데 그 결과가 표현할 수 있는 정수의 수를 초과해서 그렇게 나온 것인지 궁금합니다.


    7달 전
4개의 댓글이 있습니다.
  • Corea
    Corea

    n=9일 때, 대칭인 타일링 개수는 5개입니다. 올리신 식으로는 4개가 나오네요.


    7달 전 link
  • universalee
    universalee

    아 제가 잘못 유도해냈네요! 답변 감사드립니다!!


    7달 전 link
  • universalee
    universalee

    질문글 수정했습니다. 다시 한번 유심히 살펴주시면 감사하겠습니다!


    7달 전 link
  • universalee
    universalee

    아 이제 출력값은 옳게 나오는데 자꾸 오답처리 되네요;


    7달 전 link
  • 댓글을 남기시려면 로그인하세요.