TILING 질문드립니다. 거의 막판에 다다른것 같은데요...ㅠㅠ

  • yhtgogo
    yhtgogo

    TILING

    이 문제를 해결하려고 별짓을 조금 해봤습니다.
    각 타일의 갯수에 따르는 패턴을 발견해서
    아래와 같은 점화식을 도출해 냈습니다.

    F(N) = F(N-1) * 1 + F(N-2) * 2 + F(N-3) * 5

    그런데요.
    테스트케이스는 30000개까지에
    입력이 되는 N의 상한선이 10억이므로
    완전탐색으로 재귀적인 구현은 시간내에 불가능하구요.
    동적계획법을 이용하는 방법도 시간내에 불가능해 보였어요.
    3000만개의 테스트케이스를 위해 매번 재계산 할필요 없이
    10억개를 미리 깔아놓는 것도 시간내에 할짓은 아닌 것 같았어요.

    그래서 점화식의 매트릭스 특징을 발견하려고 애썼습니다.
    종이에 끄적끄적 거리면서 이면지 한 다발 써가면서
    혹시 GGGCCCDDD 의 방법처럼 될런지 하면서 말이죠.

    몇번의 삽질을 통해 마침내

    [ 1 2 5 ] [F(N-1)] = [F(N)]
    [ 1 0 0 ] [F(N-2)] = [F(N-1)]
    [ 0 1 0 ] [F(N-3)] = [F(N-2)]

    이렇게 3X3 행렬식을 만들게 되었습니다.

    여기서 2^0 부터 2^30 까지 2의 승수별로 행렬식을 미리 깔아놓고
    항등행렬에서부터 행렬식을 곱해주면서 답을 찾아내도록 했습니다.

    이렇게 되면 테스트케이스별로
    3 X 3 행렬식 최대 31개를 곱하게 되어
    3 X 3 X 3 X 31 = 837번의 정도 연산이 됩니다.

    대충 30,000 X 900 이면 27,000,000 이 되네요.
    10억보단 훨씬 적어서 시간내에 도달할 것 같습니다.

    이제 구현을 하고나서
    예제 케이스에서부터 엑셀이 계산할 수 있는
    어느정도는 맞춰봤는데요.

    오답이 나와서 좀 뭔가 변화가 필요한 것이 아닌지 궁금합니다.

    시간내에 할 수는 있을 것이지만 뭔가 2%가 부족한것이 무엇인지요....

    나이가 많은 것은 아닌데 머리가 안돌아가요. ㅠㅠ
    힌트라도 좀 주셨으면 좋겠습니다.^^

    #include <stdio.h>
    #define MAX_BITS 31
    #define BIG 9901
    int main(){
        int x[MAX_BITS][3][3] = {{{1,2,5},{1,0,0},{0,1,0}}};
        int w[3][3];
        int z[3];
        int test_count;
        int i, k, n;
        int row, col;
        int result;
    
        //Initialize...  Generate [power(2, i)] Matrix.
        for(i = 1 ; i < MAX_BITS ; ++i){
            for(row = 0 ; row < 3 ; ++row){
                for(col = 0 ; col < 3 ; ++col){
                    //x[i][row][col] = 0;
                    for(k = 0 ; k < 3 ; ++k){
                        x[i][row][col] += x[i-1][row][k] * x[i-1][k][col];
                        x[i][row][col] %= BIG;
                    }
                }
            }
        }
    
        //Get TestCase Count
        scanf("%d", &test_count);
        while(test_count--){
            scanf("%d", &n);
            //Generate Identity Matrix
            for(row = 0 ; row < 3 ; ++row){
                for(col = 0 ; col < 3 ; ++col){
                    if(row == col){
                        w[row][col] = 1;
                    }
                    else{
                        w[row][col] = 0;
                    }
                }
            }
            //Generate Solution
            i = 0;
            while(n > 0 && i < MAX_BITS){
                if(n & 0x01){
                    for(row = 0 ; row < 3 ; ++row){
                        for(col = 0 ; col < 3 ; ++col){
                            //Matrix Multiply
                            z[col] = 0;
                            for(k = 0 ; k < 3 ; ++k){
                                z[col] += w[row][k] * x[i][k][col];
                                z[col] %= BIG;
                            }
                        }
                        for(col = 0 ; col < 3 ; ++col){
                            w[row][col] = z[col];
                        }
                    }
                }
                n >>= 1;
                ++i;
            }
            result = w[0][0];
    
            printf("%d\n", result);
        }
        return 0;
    }
    



    3년 전
6개의 댓글이 있습니다.
  • seico75
    seico75

    저는 위와 같은 점화식이 나오지 않는데 어떻게 나온건지 설명부탁해도 될까요?
    제가 유도한 식으로는 n=4 일때 20이 나오고,
    하신 방법으로는 21이 나오는 것 같습니다.


    3년 전 link
  • WeissBlume
    WeissBlume

    행렬의 빠른 제곱을 이용하는 접근은 옳은데, 점화식이 틀린 것 같네요.저는 n=4일 때 23이 나옵니다.


    3년 전 link
  • seico75
    seico75

    다시 해보니 놓친 경우가 있어서, 23 이 맞는 것 같네요.
    그런데 행렬을 쓰려면 행렬이 커질 것 같은데... 6x6 ??


    3년 전 link
  • yhtgogo
    yhtgogo

    @seico75
    F(N-1) 은 긴 작대기 하나를 놓고 까는 방법이라 넣었구요.
    F(N-2) 는 세로로 [ㄱㄴ] [ㄴㄱ] 으로 놓고 까는 방법이라 2를 곱하구요.
    F(N-3) 은 [상병계급장] 가로작대기 하나 위에 놓고 밑에 ㄴㄱ, ㄱㄴ 가로로 놓고, 가로작대기 하나 밑에 놓고 위에 ㄴㄱ, ㄱㄴ을 놓으면 다섯가지가 되더라고요. 그래서 5를 곱했습니다.
    뭔가 빠진걸까요?


    3년 전 link
  • yhtgogo
    yhtgogo

    @WeissBlume
    감사합니다. 힌트를 점화식으로 알려주셔서 ㅎㅎㅎ
    계속 그림그리기 하고 있습니다.

    이면지 금방 쓰네요.
    아직 답을 찾지 못햇습니다.


    3년 전 link
  • yhtgogo
    yhtgogo

    방금 그림을 더 그려봤습니다.....
    와 정말 이건 뭐... 정말 어렵네요.
    1 2 5 2 2 4 2 2 4 ..... 무한정 늘어날듯 한데요.
    점화식 간에 방정식만들어서 항 소거를 해봐야겠습니다.
    정말 고맙습니다^^


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