글 읽기 - dp로 풀었는데 반례 부탁드립니다

lovelydays95 4년 전 0

예제는 다 맞는데 어디가 오류인지 모르겠습니다

#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

#define MAXSIZE 17
int map[MAXSIZE][MAXSIZE];
int cache[MAXSIZE][MAXSIZE][3];
int N;
int ans;

int dp(int y, int x, int type)
{
    if(x==N&&y==N)
        return 1;
    if(x>N||y>N)
        return 0;
    int &ret = cache[y][x][type];
    if(ret!=-1)
        return ret;
    
    ret = 0;
    switch (type) {
        case 0:
        {
            if(!map[y][x])
               ret = dp(y,x+1,0) + dp(y+1,x+1,2);
            else
                return 0;
            break;
        }
        case 1:
        {
            if(!map[y][x])
                ret = dp(y+1,x,1) + dp(y+1,x+1,2);
            else
                return 0;
            break;
        }
        case 2:
        {
            if(!map[y][x]&&!map[y-1][x]&&!map[y][x-1])
                ret = dp(y,x+1,0) + dp(y+1,x,1) + dp(y+1,x+1,2);
            else
                return 0;
            break;
        }
        default:
            return 0;
            break;
    }
    
    return ret;
}

int main(void)
{
    cin>>N;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin>>map[i][j];
    
    memset(cache,-1,sizeof(cache));
    ans = dp(1,2,0);
    cout<<ans<<endl;
}

djm03178 4년 전 5

끝이 막혀있지 않다는 이야기는 없습니다.

lovelydays95 4년 전 0

그래도 틀렸다고 나옵니다.. ㅠㅠ

djm03178 4년 전 1

어떻게 고쳤는지 보여주시지 않았는데, 어떻게 다음 반례를 찾아드릴 수 있을까요?

lovelydays95 4년 전 0

죄송합니다 ㅠㅠ

#include <iostream>
#include <math.h>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

#define MAXSIZE 17
int map[MAXSIZE][MAXSIZE];
int cache[MAXSIZE][MAXSIZE][3];
int N;
int ans;

int dp(int y, int x, int type)
{
    if(map[N][N]==1)
        return 0;
    if(x==N&&y==N)
        return 1;
    if(x>N||y>N)
        return 0;
    int &ret = cache[y][x][type];
    if(ret!=-1)
        return ret;
    
    ret = 0;
    if(type==0)
        {
            if(!map[y][x])
               ret = dp(y,x+1,0) + dp(y+1,x+1,2);
            else
                return 0;
        }
    else if(type==1)
        {
            if(!map[y][x])
                ret = dp(y+1,x,1) + dp(y+1,x+1,2);
            else
                return 0;
        }
    else
        {
            if(!map[y][x]&&!map[y-1][x]&&!map[y][x-1])
                ret = dp(y,x+1,0) + dp(y+1,x,1) + dp(y+1,x+1,2);
            else
                return 0;
        }
    
    return ret;
}

int main(void)
{
    cin>>N;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            cin>>map[i][j];
    
    memset(cache,-1,sizeof(cache));
    ans = dp(1,2,0);
    cout<<ans<<endl;
}

djm03178 4년 전 2

다음이 반례입니다.

lovelydays95 4년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dp로 풀었는데 반례 부탁드립니다

lovelydays95 4년 전 0

djm03178 4년 전 5

lovelydays95 4년 전 0

djm03178 4년 전 1

lovelydays95 4년 전 0

djm03178 4년 전 2

lovelydays95 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말