글 읽기 - 2618 경찰차 문제. 반례 찾아주세요

jina3453 5년 전 0

테스트시 뭔가 틀렸다고 하는데,

같은 거리에 떨어져있을때 누가먼저할지도 정하고했는데, 어떤부분에서 틀렸는지 잘 모르겠네요

도와주세요ㅠㅠㅠ....

#include <iostream>

using namespace std;

typedef struct pos{
    int x, y;
} pos;

pos accidents[1005];
int accident;

int abs (int a)
{
    return a>0?a:a*-1;
}
int getDistance(int a, int b)
{
    int dx = accidents[a].x - accidents[b].x;
    int dy = accidents[a].y - accidents[b].y;
    return abs(dx) + abs(dy);

}

int dt[1005][1005];
int police[1005];
int memoization(int police1, int police2, int idx)
{
    if(idx == accident+2)
    {
        dt[police1][police2] = 0;
    }

    else if(dt[police1][police2] == 0)
    {
        int pick1 = memoization(idx, police2,idx+1) + getDistance(police1, idx);
        int pick2 = memoization(police1,idx,idx+1) + getDistance(police2, idx);

        if(pick1 > pick2)
        {
            police[idx] = 2;
            dt[police1][police2] = pick2;
        }
        else
        {
            police[idx] = 1;
            dt[police1][police2] = pick1;
        }
    }
  //  cout << police1 <<" , "<< police2 << " : "<< dt[police1][police2] << endl;
    return dt[police1][police2];
}

int main()
{
    int n;
    cin >> n;
    
    cin >> accident;

    accidents[0] = (pos) {1,1};
    accidents[1] = (pos) {n,n};

    for(int i=2;i < accident+2;i++)
    {
        cin >> accidents[i].x >> accidents[i].y ;
    }
    cout << memoization(0,1,2) << endl;

    for(int i=2;i<accident+2;i++)
        cout << police[i] << endl;

}

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

문제

문제

출처

ICPC

2618 경찰차 문제. 반례 찾아주세요

jina3453 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말