BALLPAINTING 관련 질문드려요..

  • qwoowp
    qwoowp

    많이들 잘 푸시는것 같은데.. 전... 안되네요..

    아래 소스에서 잘못된 것이 있나요?

    문제를 이해를 못한 것인지... ㅠ.ㅠ.;;;

    동적계획법을 이용한 칠한 횟수별 위치에 따른 다음 잔량에 대한
    칠할 수 있는 갯수를 캐쉬에 저장하여 중복 계산하지 않도록 하였는데.

    #pragma warning(disable:4996)
    #include
    #include
    #include
    #include
    #include
    #include

    using namespace std;

    int N;
    int ball[2][1001];
    int cache[2][1001][1001*2];
    #define MOD 1000000007

    double search(vector& path)
    {
    return 0.0;
    }

    int dirx[8] = { 1, 1, 1, 0, -1, -1, -1, 0};
    int diry[8] = {-1, 0, 1, 1, 1, 0, -1,-1};

    int Cnt = 0;
    int solve(int x, int y, int n)
    {
    if(n == 2*N)
    {
    Cnt ++;
    return 1;
    }
    // int ret;
    int &ret = cache[y][x][n];
    if(ret != -1) return ret;

    ret =0;

for(int i=0; i <8 ; i++)
{
    int dy = y+diry[i];
    int dx = x+dirx[i];
    //칠해져 있으면 진행할 수 없으므로 
    if(dx == N ||dy == 2 || dx < 0 || dy < 0) 
        continue;

    if(ball[dy][dx] != 1)
    {
        ball[dy][dx] = 1;
        ret += (solve(dx, dy, n+1)%MOD);
        ball[dy][dx] = 0;
    }
}

return ret;

    }

    int main()
    {
    int cases;
    // freopen("D:\MyProject\CodeJam\연습\SampleCode\a.in","r",stdin);
    scanf("%d", &cases);
    while(cases--)
    {
    Cnt = 0;
    memset(cache, -1, sizeof(cache));
    memset(ball, 0, sizeof(ball));
    scanf("%d ", &N);
    if(N == 0)
    {
    printf("0\n");
    continue;

    }
    int ret = 0;

    //for(int x = 0; x < N; x++)
    //{
    //  for(int y=0; y<2; y++)
    //  {
        ball[0][0] = 1;
        ret = (solve(0,0, 1) % MOD);

        ret  *= (2*N);
        ret %= MOD;
        //ret  *= N;
        //ret %= MOD;
    //  }
    //}
    //printf("%d : ", Cnt);
    printf("%d\n", ret);        

}

    }


    10년 전
1개의 댓글이 있습니다.
  • mongsiry014
    mongsiry014

    문제에 나온 예제를 보니까 첫줄에 입력되는 값이 case 횟수가 아닌 것 같은데요.
    입력 값이 1, 2, 3, 0 이고 출력 값이 2, 24, 480 이였는데
    1을 입력하면 결과값 2가 나오고
    2를 입력하면 결과값 24가 나오고
    3을 입력하면 결과값 480이 나오고
    0을 입력하면 프로그램 종료를 뜻하는 것 같아요.
    이렇게 이해하고 문제 푸니까 통과되더라구요.
    저는 동적계획법 보다는 수열관계(n+1번째 항과 n번째 항과의 관계)를 추론하는 방법을 추천해요. 코드가 10줄 미만으로 풀리네요


    10년 전 link

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