글 읽기 - 할 일 정하기 DP문제 질문입니다

sontg123 3년 전 0

시간초과를 어떻게 해결해야 할지 모르겠습니다

N이 20이라고 가정하고 지금까지 이미 일이 정해진 곳을 bitmask로 처리하며 백트래킹 방식으로 DP를 돌리는데

이전에 같은 bitmask가 계산되어 있으면(예를들어 20번이 19번째일을하고 19번이 20번째 일을 한경우와 20번째가 20번째일을하고 19번째가 19번째일을 한 경우 18번째 들어갈때 bitmask가 같으므로 )

map의 key의 값이 존재하면 return 하게 하는 방식으로 메모제이션을 햇습니다

더이상의 아이디어가 없는데 코드가 잘못된건지 제 생각이 틀린건지 봐주실분 계실까요

------------------------------------------

코드 수정했습니다 후아 이틀째 못푸는중이라 점점 화나는데 아직도 시간초과가 안잡힙니다

TSP알고리즘으로 하여 마지막 사람부터 자신의 일을 정하고 다음사람으로 내려가는 방식으로 짰습니다

문제가무엇일까요

#include <iostream>
#include <vector>
#include <map>
#define INF 100000000
using namespace std;
class work_min{
private:
    vector<map<int,int>> dp;
    vector<vector<int>> val;
    int N;
public:
    work_min(){
        std::cin >>N;
        val.resize(N+1,vector<int>(N+1));
        dp.resize(N+1);
        set_val();
    }
    void set_val(){
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
                std::cin >> val[i][j];
    }

    void start_dp(){
        int bitmask=1;
        std::cout << DP(N,bitmask);
    }
    int DP(int n,int bitmask){
        if(dp[n][bitmask])
            return dp[n][bitmask];
        if(bitmask==(1<<N+1)-1)
            return 0;
        int tmp=INF;
        for(int i=1;i<=N;i++){
            if(!(bitmask&(1<<i))){
                bitmask|=(1<<i);
                tmp=min(tmp,DP(n-1,bitmask)+val[n][i]);
                bitmask&=~(1<<i);
            }
        }
        dp[n][bitmask]=tmp; 
        return dp[n][bitmask];
    }

    
};
int main(){
    work_min wm;
    wm.start_dp();
    return 0;
}

sontg123 3년 전 0

하루종일 고생해서 풀었습니다

map으로 하면 인덱스 검색 속도가매우 느린가 봅니다

그냥 vector<int>(1<<N)으로 초기화 하면 통과됩니다..

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