GRID 문제 이해가 안됩니다 도와주세요!

  • sclee1
    sclee1

    GRID 문제를 풀고 있는데요..

    완전 탐색으로는 풀었는데 시간 초과때문에 구글 검색해서 다른 사람의 해답을 보고 이해하고 있는데

    이해조차 안되서 여기다 남깁니다.

    출처 : 구글에서 검색

    인데요, 점화식을 어떻게 이렇게 세웠는지 이해가 가질 않습니다. 대강 재귀적으로 하면 될거같아서 몇번 시도해보았는데

    이해가 안되네요.

    점화식은 아래와 같습니다!

    해법
    점화식 세우는 것이 관건.
    An, Bn, Cn으로 나누어서 점화식을 다음과 같이 세웠다.
    An = A(n-1)+A(n-2)+2*B(n-1)+Cn : n번째 너비만큼 채우는 방법의 수
    Bn = A(n-1)+B(n-1) : n번째 너비만큼 모서리2칸을 비운 나머지를 모두 채우는 방법의 수
    Cn = A(n-2)+C(n-2) : n번째 너비만큼 'ㄷ'형태로 채우는 방법의 수
    각 점화식의 초항(n=0~2까지)은 간단하기 때문에 손으로 구했다.

    혹시 도와주실 분 계신가요?

    아 근데 더 간단한 솔루션을 방금 찾았습니다.

    출처 : 구글에서 검색

    여기에 아래에 보시면 간단하게 점화식으로 구해서 풀었는데요,

    int main(){
    unsigned int dp[1001];
    dp[0] = dp[1] = 1; dp[2] = 5; dp[3] = 11;

    for(int i = 4;i <= 1000;++i)
    dp[i] = dp[i-1]+5*dp[i-2]+dp[i-3]-dp[i-4];

int T,n;

scanf("%d",&T);

for(int tc = 1;tc <= T;++tc){
    scanf("%d",&n);
    printf("%d %u\n",tc,dp[n]);
}

return 0;

    }

    왜 마지막에 dp[i-4]를 뺴줬는지 이해가 안가네요.


    8년 전
1개의 댓글이 있습니다.
  • JongMan
    JongMan

    가장 무식하게는 c(i, mask) = i번째 세로줄을 채울 차례이고, i-1번째 세로줄에서 쓴 가로 도미노가 이번 줄로 넘어오는 가로줄들을 나타내는 비트마스크를 mask라고 할 때, 나머지를 채울 수 있는 경우의 수는?

    이런 식으로 해서 dp하실 수 있겠죠. 말씀하신 것들은 아마 이 문제의 상태공간을 손으로 적절히 최적화한 것인 듯 싶네요. (mask = 0011 이나 1100 이나 답은 같을 테니)


    8년 전 link

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