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

핵심 아이디어

<aside> 💡

$n \leq 15$ 이므로 비트마스킹 DP를 사용할 수 있다. 상태공간을 다음과 같이 정의하자.

• 망토는 항상 정문 쪽에 있다.
• $dp_{state} =$ $state$인 상태가 되기 위해 필요한 시간의 최소값
• $state$의 $i$번째 비트가 켜져 있다면 $i$번째 학생은 현재 기숙사에 있는 학생이다.

정문이 학생이 두 명 있는 경우를 제외하면 나머지 인원을 위해서 한명이 다시 기숙사에서 정문으로 망토를 가져와야 한다.

정문에 있는 $i$와 $j$가 함께 기숙사로 간다고 할 때, $dp$의 전이는 다음과 같이 일어난다.

• $i$가 다시 정문으로 오는 경우: $+ a_i\ +max(a_i, a_j)$
• $j$가 다시 정문으로 오는 경우: $+ a_j\ +max(a_i, a_j)$
• 원래 기숙사에 있던 $k$가 정문으로 오는 경우: $+ a_k\ +max(a_i, a_j)$ </aside>

위 전이에서 누가 기숙사에 남게 되고 누가 다시 정문으로 오게 되는지 생각하며 코드를 짜면 된다.

당연하게도 $i,j$는 정문에 있어야 하고 $k$는 원래 기숙사에 있어야 한다.

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;
#define INF 2139062143

int n;
int a[20];

int dp[1<<15];

int go(int state)
{
    int &ret = dp[state];
    
    if(ret != INF) return ret;

    if(__builtin_popcount(state) == 2){
        ret = 0;
        for(int i = 0; i<n; i++){
            if(state&(1<<i)){
                ret = max(ret, a[i]);
            }
        }

        return ret;
    }

    for(int i = 0; i<n; i++){
        if((state&(1<<i)) == 0) continue;
        for(int j = 0; j<n; j++){
            if((state&(1<<j)) == 0 || (i == j)) continue;

            for(int d = 0; d<n; d++){
                if((state&(1<<d)) == 0){
                    ret = min( ret, go(((state|(1<<d))^(1<<i))^(1<<j)) + a[d] + max(a[i], a[j]) );
                }

                else if(d == i){
                    ret = min( ret, go((state^(1<<j))) + a[i] + max(a[i], a[j]));
                }
                else if(d == j){
                    ret = min( ret, go((state^(1<<i))) + a[j] + max(a[j], a[i]));
                }
            }
        }
    }
    
    return ret;
}

signed main()
{
    FASTIO;
    cin >> n;
    for(int i = 0; i<n; i++){
        cin >> a[i];
    }

    memset(dp, 0x7f, sizeof(dp));
    
    cout << go((1<<n)-1) <<"\\n";
    
    return 0;
}