발전소

 

배낭문제(TSP)

관련문제 

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

풀이

2020/02/13 - [BOJ/C++] - 외판원 순회

불러오는 중입니다...

 

17번째 줄 현재 메모이제이션 한 status값을 가져올 때 주소값을 가져오지 않으면 TLE가 발생한다. 

왜일까..

#include <iostream>
#include <vector>
#define MAXX 17
#define INF 987654321
using namespace std;
 
int n, goal;
int w[MAXX][MAXX], dp[1 << MAXX];
 
int tsp(int cnt, int status) {
    //status는 현재 켜져있는 발전소는 1로 표시가 되어있다. 
    if (cnt == goal) {
        //목표 달성 
        return 0;
    }
 
    int &ret = dp[status];
 
    if (ret != INF) return ret;
    //이미 한 번 방문 했음 
    
    for (int i = 0; i < n; i++) {
        if ((status & (1 << i)) > 0) {
            // cout << "debug " << status << " " << (status & (1 << i)) << '\n';
            //켜져있는 발전소라면 
            //다른 발전소를 켤 비용을 비교한다. 
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
 
                if ((status & (1 << j)) == 0) {
                    //켜야 할 발전소 
                    ret = min(ret, w[i][j] + tsp(cnt+1, (status | (1 << j))));
                }
            }
        }
    }
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> w[i][j]; //i번 발전소가 j번 발전소를 켜는데 드는 비용
        }
    }
 
    for (int j = 0; j < (1 << n); j++)
    {
        dp[j] = INF;
    }
 
    string s;
    cin >> s;
 
    int status = 0, cnt = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == 'Y')
        {
            status |= (1 << i);
            cnt++;
        }
    }
 
    // cout << "debug " << status << '\n';
    cin >> goal; //켜져야 하는 발전소의 개수
 
    //모두 꺼져있을 때 goal이 1이상이면 -1
 
    if (!cnt) {
        // 켜진 발전소의 개수가 0일 때 목표가 0이면 0 
        if (!goal) cout << 0 << '\n';
        else cout << -1 << '\n';
    }
    else if (cnt >= goal) cout << 0 << '\n';
    else
    {
        cout << tsp(cnt, status) << '\n';
    }
 
    return 0;
}