글 읽기 - 2618 경찰차 문제 DP 왜 틀렸을까요

opencluster 3년 전 0

최소거리는 dp로 풀었고

경로 찾는 것은 dp하면서 i,j가 1차이날때 i나 j가 어디에서 왔는지 기록하는 배열을 만든 다음

i와 j가 1 차이 날때까지 뺀 다음 이 배열을 불러와서 재귀함수 했습니다..

왜 틀렸을까요? 테케 몇개 만들어서 더 넣어봐도 안되네요

제생각에는 경로 찾는 것에서 틀린 거 같은데 감이 안잡히네요

#include <stdio.h>
#include<iostream>
#include<stack>
using namespace std;
int n,cas;
typedef struct a
{
    int x;
    int y;
} type;
type c[1002];
int memo[1002][1002];
int ibigfrom[1002];
int jbigfrom[1002];
int abs(int k)
{
    if(k>0) return k;
    else return (-k);
}
int dist(type a, type b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}
void print()
{
    for(int i=0; i<=cas; i++)
    {
        for(int j=0; j<=cas; j++)
            printf("%d ",memo[i][j]);
        printf("\n");
    }
}
stack<int> S;
void findfrom(int x,int y)
{
    if(x==0)
    {
        while(y--) S.push(2);
        return;
    }
    else if(y==0)
    {
        while(x--) S.push(1);
        return;
    }

    if(x>y)
    {
        int k=x-y;
        while(k--) S.push(1);
        findfrom(ibigfrom[y+1],y);
    }
    else
    {
        int k=y-x;
        while(k--) S.push(2);
        findfrom(x,jbigfrom[x+1]);
    }
}
int main()
{
    scanf("%d %d",&n,&cas);
    for(int i=1; i<=cas; i++) scanf(" %d %d",&c[i].x,&c[i].y);
    memo[0][1]=abs(n-c[1].x)+abs(n-c[1].y);
    memo[1][0]=abs(1-c[1].x)+abs(1-c[1].y);
    for(int i=2; i<=n; i++)
    {
        memo[i][0]=memo[i-1][0]+dist(c[i],c[i-1]);
        memo[0][i]=memo[0][i-1]+dist(c[i],c[i-1]);
    }
    for(int i=1; i<=cas; i++)
    {
        for(int j=1; j<=cas; j++)
        {
            if(i==j) continue;
            if(i>j)
            {
                if(i-j!=1)
                {
                    memo[i][j]=memo[i-1][j]+dist(c[i],c[i-1]);
                }
                else
                {
                    int Min;
                    Min=memo[0][j]+abs(1-c[i].x)+abs(1-c[i].y);
                    for(int k=1; k<j; k++)
                    {
                        int ifMin=memo[k][j]+dist(c[i],c[k]);
                        if(ifMin<Min)
                        {
                            Min=ifMin;
                            ibigfrom[i]=k;
                        }
                    }
                    memo[i][j]=Min;
                }
            }
            else
            {
                if(j-i!=1)
                {
                    memo[i][j]=memo[i][j-1]+dist(c[j],c[j-1]);
                }
                else
                {
                    int Min;
                    Min=memo[i][0]+abs(n-c[j].x)+abs(n-c[j].y);
                    for(int k=1; k<i; k++)
                    {
                        int ifMin=memo[i][k]+dist(c[j],c[k]);
                        if(ifMin<Min)
                        {
                            Min=ifMin;
                            jbigfrom[j]=k;
                        }
                    }
                    memo[i][j]=Min;
                }
            }
        }
    }
    int Min=memo[0][cas];
    int Mini;
    int Minj;
    for(int i=1; i<cas; i++)
        if(memo[i][cas]<Min)
        {
            Min=memo[i][cas];
            Mini=i;
            Minj=cas;
        }
    for(int i=0; i<cas; i++)
        if(memo[cas][i]<Min)
        {
            Min=memo[cas][i];
            Mini=cas;
            Minj=i;
        }
    printf("%d\n",Min);
    findfrom(Mini,Minj);
    while(!S.empty())
    {
        printf("%d\n",S.top());
        S.pop();
    }
}

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

문제

문제

출처

ICPC

2618 경찰차 문제 DP 왜 틀렸을까요

opencluster 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말