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

  • 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

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.