글 읽기 - 4243 질문이요

shinhj88 10년 전 0

몇일째 시도 했는데 풀리지 않아서 질문올립니다.

점화식은 D[왼쪽까지 탐색][오른쪽까지탐색][현재 왼쪽/오른쪽]=총걸린시간 ,현재 대기시간을 저장해서 최소값을 구했는데 자꾸 오답이 뜹니다.
어디서 잘못됬는지 조언 부탁드립니다.

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
const long MAX_T=150000000000;
int S,N;
vector<int> DATA;
pair<long,long> D[101][101][2];
void input()
{
        scanf("%d%d",&N,&S);
        
        S--;
        DATA.clear();
        DATA.reserve(N+1);
        DATA.push_back(0);
        long s=0;
        for(int i=0;i<N-1;i++)
        {
                int a;
                scanf("%d",&a);
                s+=a;
                DATA.push_back(s);

        }


}
pair<long,long> mkvalue(const pair<long,long> &a, long cost)
{
        pair<long,long> ret;
        ret.second=a.second+cost;
        ret.first=a.first+ret.second;
        return ret;
}
pair<long,long> cmp(const pair<long,long> &a,const pair<long,long> &b)
{
        if(a.first<b.first)return a;
        else return b;
}
void setting()
{
        for(int i=0;i<=DATA.size();i++)
        {
                for(int j=0;j<=DATA.size();j++)
                {
                        for(int k=0;k<2;k++)D[i][j][k]=make_pair(MAX_T,MAX_T);
                }
        }
        D[S][S][0]=D[S][S][1]=make_pair(0,0);
}
long process()
{
        setting();
        int c=DATA.size();
        c=max(S,c-S);
        for(int i=0;i<=100;i++)
        {
                for(int j=0;j<=100;j++)
                {
                        for(int k=0;k<=100;k++)
                        {
                                for(int t=0;t<2;t++)
                                {
                                if(S-j==S||S+j==S)continue;
                                if(S-j<S&&S+k<DATA.size()&&S-j>=0)
                                {
                                        int l=S-j;
                                        int r=S+k;
                                        long P=DATA[l];
                                        pair<long,long> &ret=D[l][r][0];
                                        ret=cmp(ret,cmp(mkvalue(D[l+1][r][0],abs(DATA[l+1]-P)),mkvalue(D[l+1][r][1],abs(DATA[r]-P))));
                                }
                                if(S-k>=0&&S+j>S&&S+j<DATA.size())
                                {
                                        int l=S-k;
                                        int r=S+j;
                                        long P=DATA[r];
                                        pair<long,long> &ret=D[l][r][1];
                                        ret=cmp(ret,cmp(mkvalue(D[l][r-1][0],abs(DATA[l]-P)),mkvalue(D[l][r-1][1],abs(DATA[r-1]-P))));
                                }
                                }
                        }
                }
                if(S-i<0&&S+i>=DATA.size())break;

        }
        pair<long,long> ans=cmp(D[0][DATA.size()-1][0],D[0][DATA.size()-1][1]);
        return ans.first;
}
int main()
{
        int T;
        scanf("%d",&T);
        while(T--)
        {
             input();
             printf("%ld\n",process());
        }
        return 0;
}

baekjoon 10년 전 0

이 소스를 실행시켜보니 예제가 안나옵니다.

예제의 출력이

-1619276749

-1619276715

가 나오는데, 이걸 질문하신 건가요?

arine 10년 전 2

일단 값이 음수가 나오는 것은 integer overflow 때문인데, c에서 long type은 at least 4 byte이기 때문입니다. 상수 MAX_T의 값을 보니 의도하신 것이 8 byte 자료형인 것 같아서 long long으로 고쳤더니 예제가 나오네요.

그 다음으로 생각할 것은 점화식이 맞는가!! 인데요... 점화식을 너무 간단히 써주셔서 소스 보고 이해하는 데 좀 오래 걸렸네요..ㅜㅜ

본 문제에서 지연 시간에 해당하는 값은 생각하신대로 왼쪽에서 온 경우와 오른쪽에서 온 경우를 계산해서 최솟값을 이용해 계산할 수 있습니다. 각 문제의 부분 문제가 최적이면 그 문제도 최적이 되는 게 맞죠..

그런데 총 걸린 시간, 즉 지연 시간의 합도 이런 방식으로 구할 수 있을까요? 현재까지의 총 걸린 시간(지연 시간의 합)을 조금 크게 하는 대신 현재 위치 건물에 오는데까지 걸린 시간을 줄이면 그 후에 방문할 건물의 지연시간이 줄어들어서 결국 합이 줄어드는 경우가 있지는 않을까요?...^^;

그런 경우가 있다고 판단되신다면, 각 건물의 최소 지연시간을 이용해서(지연 시간을 부분 문제로 해서) 전체 지연시간의 합을 구하는 것을 한 번 고민해보세요..

(사실 저도 처음에 질문하신 분과 비슷한 방법으로 접근했는데, 두 번째 예제가 안 나와서 결국 다시 생각해야 했습니다. 근데 이 소스는 두 번째 예제가 나오네요! 대체 무슨 마법을 부리신 건가요...ㄷㄷ)

잘 떠오르지 않는다면 이 사이트 내의 위키에 수록된 풀이를 참조하시는 것도 좋습니다.

우선 답변해 주셔서 진심으로 감사드림니다.
그리고 이해하기 힘드셨다니.....ㅜㅜ

점화식이 D[왼쪽끝][오른쪽][현재 위치] 이고 이것을 왼쪽끝은 l 오른쪽끝을 r 현재위치를 RL로 했을때 현재위치 l 이고 경비원이 현재 왼쪽에 있다면 D[l][r][0]이 될텐데 이값은 [l-1][r][0]에 있는값과 [l-1][r][오른쪽] 에 있는 값에서 오는데 왼쪽끝에서 다시 왼쪽 즉 l-1~S까지 다되돌아가면 시간이 더 들게 뻔하니깐 현재지점 l이 방문될값은 l-1 r 왼쪽 또는 오른쪽에서 오는 값이 맞을것같앟서 그렇게 했었습니다.

제가 부른 마법은 왼쪽을 구할때 오른쪽에서 만들어진값이 갱신이되더라고요 그래서 한번더 돌리겠끔했습니다.
이해가 잘안되죠 ㅜㅜ

아무튼 이 방법이 완전히 틀린건가요????

arine 10년 전 0

질문하신 분께서 하신 대로 부분문제를 정의하면, 부분문제가 최적이라고 해서 전체 문제가 항상 최적이 되지 않습니다. 앞선 댓글에서 언급한대로, 현재까지의 지연시간의 합이 커지는 대신 현재 방문하고 있는 건물의 지연 시간을 줄이고, 다음 방문하는 건물들의 지연 시간을 줄여서 전체 지연 시간의 합이 줄어드는 경우가 있기 때문입니다.
다만 각 건물의 최소 지연시간은 최적이 되므로 그것을 이용해 지연시간 합의 최소를 구해보시길 바랍니다.^^

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

문제

문제

출처

ICPC

4243 질문이요

shinhj88 10년 전 0

baekjoon 10년 전 0

arine 10년 전 2

shinhj88 10년 전 0

arine 10년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말