[editorial] 2007년 서울 온사이트 본선 E번 Tile Code

  • hyunhwan
    hyunhwan

    제가 속했던 팀(the pulza)가 안드로메다로 여행을 떠난 이유 중 하나는 바로 이문제 때문이 아니었을까 싶습니다(실제로도 대회에서는 풀지 못했고, 대회가 끝나고 알고스팟의 중계를 보고 난 직후에야 풀게 되었던 문제입니다.)
    하지만 statistics를 봤을 경우 참가한 팀 중에서 21팀이 풀었던 문제인지라 난이도는 그리 어렵지 않다라고 평가를 할 수 있을듯 합니다.
    처음에 봤을 때 ICPC계에서 조금이라도 발을 붙이신 분이라면 떠올랐을 문제가 있을 겁니다.
    혹시 이 문제를 풀지 못하셨던 분이라면 먼저 추천해드리고 싶은 문제가 있습니다. 아직도 푸시지 못하신 분은 이 문제 부터 풀어보시길 바랍니다.
    Tiling : http://acm.pku.edu.cn/JudgeOnline/problem?id=2506
    위의 문제는 동적계획법으로 풀 수 있으며, 이 문제를 풀기 위한 점화식은 다음과 같습니다.

    D[N] : N길이의 모든 가지수
    D[N] = D[N-1] + D[N-2] * 2[/spoiler]
    E번 문제 역시 동적계획법 문제이지만, 차이점이 있습니다. 그것이 무엇인지 지금부터 설명을 하고자 합니다.
    E번 문제가 까다로왔던 이유는 다름이 아니라, 다음과 같은 그림이 동일한 경우인 한가지로 체크가 되기 때문입니다(좌우로 뒤집었을 경우 서로 동일한 모양이 나올 경우)

    A : 문제에서 요구한 조건을 고려하지 않은 모든 가지수 - 이는 Tiling 문제를 풀때 처럼 구하면 됩니다.
    B : 대칭을 이루는 모양의 가지수
    C : 좌우로 뒤집었을 경우의 동일한 모양이 나오는 경우의 수
    D : 문제에서 요구하는 답
    C = (A-B) / 2
    D = C + B

    마지막으로 남은 것은 대칭을 이루는 모양의 가지수 인데요. 길이 N에 대해서 대칭을 이루는 경우의 수는 다음과 같이 구합니다(여기서 문제 조건을 고려하지않은 길이 N에 대한 모든 경우는 P[N]으로 표기합니다.)
    우선 길이가 홀수 일경우엔 1 x 2 타일이 가운데에 세워져 있는 모양일 경우를 기준으로 대칭이 되기 때문에 P[(N-1)/2] 가 대칭을 이루는 경우가 됩니다.
    짝수의 경우엔 절반의 모양이 대칭이 되는경우와, 1 x 2 타일이 2개가 눕혀진 모양으로 2 x 2 크기로 가운데에 존재하는 경우 혹은 2 x 2 타일이 가운데에 위치한 경우가 존재하므로 가지수는 P[N/2] + 2 * P[(N-2)/2]가 됩니다.
    이것만 해결하면 아래와 같이 간결한 소스코드가 나오게 됩니다. 대회에서 못푼 문제라는 점이 아쉽긴 하지만, 꽤나 재미있는 문제 중에 하나가 아니었나 싶습니다.

    #include <iostream>
    using namespace std;
    typedef long long ll;
    ll p[31]; // 문제 조건을 고려하지 않은 가지수를 저장한 테이블
    ll d[31]; // N에 대한 답을 저장하는 테이블 
    void prepare() {
        p[1] = 1; p[2] = 3;
        for(int i=3;i<=30;++i) p[i] = p[i-1] + p[i-2] * 2;
        d[1] = 1; d[2] = 3;
        for(int i=3;i<=30;++i) {
            ll B;
            if(i%2==1) { B = p[(i-1)/2]; }
            else { B = p[i/2] + 2 * p[(i-2)/2]; }
            d[i] = (p[i]-B) / 2 + B;
        }
    }
    int main() {
        prepare();
        int T, N;
        cin >> T;
        while(T--) {
            cin >> N;
            cout << d[N] << endl;
        }
    }
    
    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
3개의 댓글이 있습니다.
  • legend12
    legend12

    전형적인 DP 문제~!
    점화식에 Boundary Condition 도 써주세요 ㄲㄲ


    16년 전 link
  • soyoja
    soyoja

    뒷북일수도 있겠는데... 본문에 오타가 하나 있습니다... ^^
    중간의 해법 설명에서 D = C+A 가 아니고 D = C+B 입니다...


    16년 전 link
  • hyunhwan
    hyunhwan

    이제서야 답글을보고 수정하게 되었네요 ㅠ_ㅡ


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