2320 - 끝말잇기

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

단어를 첫글자와 마지막글자로 압축하고 재귀로 다음 단어가 가능하다면 진행하도록 했다.

매번 0~N-1 번째 단어를 모두 확인해야한다. (선택한 단어에 따라 가능한 단어가 바뀌기 때문)

이렇게 하면 16^16 인 것같다. 너무 많다. (16! 일수도 있는데 이것도 큼) 단어를 선택함에 있어서 순서만 다르고 조합이 같은 중복 선택(호출)이 분명 존재한다.

AE EA UA AU 같은 경우는 AE-EA-AU-UA 도 되지만, AU-UA-AE-EA 도 된다. (둘은 같다)

IE EE EI EO 는 EI-IE-EE-EO 도 되지만 EE-EI-IE-EO 도 된다. EO 입장에선 앞에서 무슨 순서로 오는 건 상관없다. 어떤 것을 사용했는가만 알면 된다.

N=16 이니까 n번째 단어를 사용했다/안했다고 표현하면 2^16 으로 표현이 가능하다. 그럼 재귀식은 (현재 위치, 이전까지 사용한 단어의 상황) 으로 중복을 제거할 수있다.

#include <bits/stdc++.h>
using namespace std;

int n, score[16];
char s[16][3];
bool visit[16];
int dp[16][1<<16+1];

int f(int pos, int bit){
    if(pos >= n) return 0;
    int& r = dp[pos][bit];
    if(r != -1) return r;
    
    r = 0;
    visit[pos] = true;
    for(int i=0; i<n; ++i){
        if(!visit[i] && s[pos][1] == s[i][0]){
            r = max(r, f(i, bit | (1<<i)));
        }
    }
    visit[pos] = false;
    return r += score[pos];
}

int main(){
    scanf("%d ", &n);
    for(int i=0; i<n; ++i){
        char t[101];
        scanf("%s ", t);
        s[i][0] = t[0];
        s[i][1] = t[strlen(t)-1];
        score[i] = strlen(t);
    }
    
    memset(dp, -1, sizeof(dp));
    int r = 0;
    for(int i=0; i<n; ++i){
        memset(visit, false, sizeof(visit));
        int k = f(i, 1<<i);
        r = max(r, k);
    }
    printf("%d", r);
    
    return 0;
}