글 읽기 - 김치 배달문제 질문이요..

smu201111192 7년 전 0

go(a,b,where,time)

a~b위치에 김치 배달을 모두 완료한상태고

where==0 현재 a위치에 있음

where==1 현재 b위치에 있음

time=a~b구간 김치 배달을 하는데 걸린시간 총시간

이런식으로 재귀로 짜봣는데 자꾸 wa 가뜨네요.

제가 실수한 부분이 있나요?

테케는 다잘나오는데 어느부분이 틀렸는지 잘 모르겠습니다. ㅠ

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
long long  n,start;
vector<long long > v;
long long min(long long a,long long b){
    if(a<b)return a;
    return b;
}
long long dp[1001][1001][2];
long long go(long long  a,long long  b,long long  where,long long  time){
    if(a==0 && b==v.size()-1)return 0;
    long long &ans=dp[a][b][where];
    if(ans!=-1)return ans;
    ans=1e9;
    if(a!=0){
        long long  dist=where==0 ?abs(v[a]-v[a-1]) :abs(v[b]-v[a-1]);
        long long  temp=time+dist;
        ans=min(ans,go(a-1,b,0,temp)+temp);
    }
    if(b!=v.size()-1){
        long long  dist=where==0 ?abs(v[a]-v[b+1]) :abs(v[b]-v[b+1]);
        long long  temp=time+dist;
        ans=min(ans,go(a,b+1,1,temp)+temp);
    }
    //cout<<a<<' '<<b<<' '<<where<<' '<<time<<' '<<ans<<endl;
    return ans;
}
int  main(){
    ios::sync_with_stdio(false);
    cin>>n>>start;
    memset(dp,-1,sizeof(dp));
    for(long long  i=0;i<n;i++){
        long long  num;
        cin>>num;
        if(num!=start)
            v.push_back(num);
    }
    v.push_back(start);
    sort(v.begin(),v.end());
    long long  sIndex=lower_bound(v.begin(),v.end(),start)-v.begin(); //시작점의 위치를 찾는다
    cout<<go(sIndex,sIndex,0,0);
    return 0;
}

baactree 7년 전 0

time까지 메모이제이션 하시던감

time을 없애시던감

smu201111192 7년 전 0

답변감사합니다. 박트리님 ㅎ

근데 time변수가 dp배열을 채우는데 영향을 주고 있는건가요?

잘 이해가 안가네요 ㅠ

smu201111192 7년 전 0

a~b까지 김치배달을 하는데 최적의 시간!=time 일 수도 있어서 그런가요?

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

문제

문제

출처

ICPC

김치 배달문제 질문이요..

smu201111192 7년 전 0

baactree 7년 전 0

smu201111192 7년 전 0

smu201111192 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말