ASYMTILING 코드 오답 문의

  • chochogogo
    chochogogo

    3번째 case에서 오답이 나옵니다...
    제가 생각한 문제 풀이 알고리즘은
    현재 타일의 빈 공간의 최 좌측, 최 우측에서부터 타일을 채워 나간다고 가정했을 때
    각 case는

    |?????| //빈 공간의 제일 왼쪽, 오른쪽에 새워서 한개씩
    |?????= //빈 공간의 제일 왼쪽에 세워서 한개, 오른쪽에 눞혀서 두개
    =????| //빈 공간의 제일 왼쪽에 눞혀서 두개, 오른쪽에 세워서 한개
    =????= //빈 공간의 제일 왼쪽, 오른쪽에 눞혀서 두개씩

    이며,
    놓을수 있는 칸이 없거나 한개만 놓을 수 있는 케이스에서
    현재 상태까지가 대칭인지 여부를 통해 기저사례를 처리하는
    방식입니다...

    혹시 제 알고리즘이나 코드에 문제가 있으면 지적 부탁드립니다.
    감사합니다!

    #include <stdio.h>
    
    #define MOD_NUM 1000000007
    
    void input(void);
    void solve(void);
    long long solving(int fromLeftStartPos, int fromRightStartPos, int isSymmetry);
    
    long long cache[105][105][2];
    int N;
    
    int main(void)
    {
        int tc, T;
        freopen("input.txt", "r", stdin);
        scanf("%d", &T);
    
        for (tc = 1; tc <= T; tc++)
        {
            input();
            solve();
        }
    
        return 0;
    }
    
    void input(void)
    {
        scanf("%d", &N);
    }
    
    void solve(void)
    {
        for (int i = 0; i <= N; i++)
            for (int j = 0; j <= N; j++)
                for (int k = 0; k < 2; k++)
                    cache[i][j][k] = -1;
    
        printf("%lld\n", solving(0, N - 1, 1));
    }
    //현재까지의 대칭상태가 isSymmetry 이고(1 : 대칭, 0 : 비대칭), fromLeftStartPos, fromRightStartPos 서부터 고려하여 타일을 놓는다고 가정했을 때 놓을 수 있는 가지 수
    long long solving(int fromLeftStartPos, int fromRightStartPos, int isSymmetry)
    {
        //기저 사례
        if (fromRightStartPos - fromLeftStartPos < -1)
            return 0;
        else if (fromRightStartPos - fromLeftStartPos == -1 || fromRightStartPos - fromLeftStartPos == 0)
        {
            if (isSymmetry == 1)    //대칭이면
                return 0;
            else
                return 1;
        }
    
        long long &ret = cache[fromLeftStartPos][fromRightStartPos][isSymmetry];
    
        if (ret != -1)
            return ret;
    
        ret = 0;
    
        ret = (solving(fromLeftStartPos + 1, fromRightStartPos - 1, isSymmetry * 1) % MOD_NUM + solving(fromLeftStartPos + 2, fromRightStartPos - 2, isSymmetry * 1) % MOD_NUM +
            solving(fromLeftStartPos + 1, fromRightStartPos - 2, isSymmetry * 0) % MOD_NUM + solving(fromLeftStartPos + 2, fromRightStartPos - 1, isSymmetry * 0) % MOD_NUM) % MOD_NUM;
    
        return ret;
    }
    

    9년 전
1개의 댓글이 있습니다.
  • SinAska
    SinAska

    점화식이 잘못되었네요
    블록을 정리할 수 있는 점화식은 아래면 충분합니다.
    점화식을 간단하게 줄이면, 작성하신 긴코드대신, 10줄정도의 코드로
    작성가능합니다.

    타일을 채울 수있는 전체 방법의 수는 아래와 같습니다.
    T(K) = T(K-1)+T(K-2)
    |() =() (세로로 세우는 방법 -> T(K-1), 가로로채우는 방법 -> T(K+2))

    대칭인 케이스는 괄호부분이 대칭이라고 가정하면,
    이 두케이스로 정리할 수 있을 것같네요.
    대칭도 메모이제이션해준후 전체경우의수에서 대칭의 수를 뺴주면
    |()| =()=

    결과는 나오게 되겠죠... 다만 전체경우의 수가 long long의 값을
    초과하므로 역modulo 연산도 필요합니다.

    우선 점화식 부터 다시 접근해보시는게 좋을듯하네요


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