SUSHI문제 해결하신분들 답변좀해주세여 ㅜㅜ

  • shinhj88
    shinhj88

    SUSHI
    이문제를 다이나믹 넵섹 문제 풀듯이 접근하였는데 메모리 낭비를 하지 않기 위해 (돈,선호도)이런식으로 순서쌍을 가져서 해결하려했는데 계속 시간초가가 나오네요 ㅜㅜ 푸신분들있으면 어떻케풀었는지 알려주세요

    이건제소스입니다

    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <queue>
    #include <deque>
    using namespace std;
    #define  oo 21474837
    typedef pair<long,long> P;
    struct input{
        long long int money,profit;
    };
    input data[21];
    int n,m;
    int ans;
    deque<P> dp[2];
    priority_queue<P,vector<P>,greater<P> >que;
    int cmp(const input &a,const input &b)
    {
        if(a.money==b.money)return a.profit>b.profit;
        return a.money<b.money;
    }
    void dynamic()
    {
        int i;
        long j;
        int past=-1;
        ans=0;
        P a,b,c;
        a.first=0;
        a.second=0;
        dp[1].push_back(a);
        for(i=0;i<n;i++)
        {
            if(past>data[i].profit)continue;
            past=data[i].profit;
            a.first=data[i].money;
            a.second=data[i].profit;
            dp[i%2].clear();
            while(!dp[(i+1)%2].empty())
            {
                b=dp[(i+1)%2].front();
                dp[(i+1)%2].pop_front();
                que.push(b);
                for(j=1;;j++)
                {
                    if(b.first+a.first*j>m)break;
                    else
                    {
                        c.first=b.first+a.first*j;
                        c.second=b.second+a.second*j;
                        que.push(c);
                    }               
                }
                while(!que.empty())
                {
                    c=que.top();
                    if(ans<c.second)ans=c.second;
                    dp[i%2].push_back(c);
                    if(dp[i%2].size()>1)
                    {
                        if(dp[i%2][dp[i%2].size()-2]>dp[i%2][dp[i%2].size()-1])dp[i%2].pop_back();
                    }
                    que.pop();
    
                }
            }
        }
    }
    int main()
    {
        int C,i;
        cin>>C;
        while(C--)
        {
            cin>>n>>m;
            m/=100;
            for(i=0;i<n;i++)
            {
                cin>>data[i].money>>data[i].profit;
                data[i].money/=100;
            }   
            sort(data,data+n,cmp);
            dynamic();
            cout<<ans<<endl;
    
        }
        return 0;
    }
    

    12년 전
3개의 댓글이 있습니다.
  • JongMan
    JongMan

    동적계획법이 아니라 다익스트라 풀듯이 접근하신 것 같은데요? ㅎㅎ

    힌트 하나: 문제에 주어진 입력의 조건을 활용하면 상태 공간 크기를 1/100으로 줄일 수 있습니다.


    12년 전 link
  • shinhj88
    shinhj88

    가격이 다 똑같고 선호도가 낮고, 가격이 높지만 선호도가 낮은 데이터는 연산할 필요가 없기 때문에 그걸처리 하지 않기 위해서 정렬를 해주었구요 그리고 입력데이터가 100의 배수로만 들어온다해서 가격을 100으로 나누어주었고요 그다음에 n번째 스시를 이용하려면 n-1개가 필요한데 여기서 합쳐진 금액이 다만들어 지지 않아서 필요한 액수와 글에 합하여진 선소도만 저장하였고 여기서 선호도가 이전선호도보다 작아지는경우 그 데이터는 유망하지 않으므로 저장하지않아 공간을 줄여나갔는데 문제는시간이 너무 걸린다는 거입니다.


    12년 전 link
  • hyunhwan
    hyunhwan

    우선 DP를 하셨다고 했는데, 그렇다면 상태공간에 대해 계산된 결과를 저장하는 배열이 있어야 할 것 같은데 그런게 보이질 않는것 같습니다. 이러한 배열이 없을경우 하나의 상태공간에 대해 중복연산이 발생해서 ㅖ상했던 수행시간보다 많은 수행시간을 필요로 할 것 같습니다.


    12년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.