끝말잇기

백준 2320번: 끝말잇기

아이디어

마지막 문자가 X이고, 지금까지 사용한 단어 목록을 Y라 하자. 이 상태에서 낼 수 있는 가장 높은 점수를 cache[X][Y]에 메모이제이션 ㄱㄱ

코드

#include <bits/stdc++.h>

using namespace std;

int N;
string words[16];
int cache[5][1<<16]; // aeiou

int getcharnum(string s, int idx) {
    if (s[idx] == 'A') return 0;
    else if (s[idx] == 'E') return 1;
    else if (s[idx] == 'I') return 2;
    else if (s[idx] == 'O') return 3;
    else if (s[idx] == 'U') return 4;
    else return -1;
}

int solve(int lastword, int cur) {
    if (cur == (1<<N)-1) return 0;
    
    int lastchar = getcharnum(words[lastword], words[lastword].size()-1);
    int& ret = cache[lastchar][cur];
    if (ret != -1) return ret;
    
    ret = 0;
    for (int i = 0; i < N; i++) {
        if (cur&(1<<i)) continue;
        if (lastchar != getcharnum(words[i], 0)) continue;
        ret = max(ret, solve(i, cur|(1<<i)) + (int)words[i].size());
    }
    return ret;    
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> words[i];
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        memset(cache, -1, sizeof(cache));
        ans = max(ans, solve(i, 1<<i) + (int)words[i].size());
    }
    cout << ans;
    return 0;
}

여담

풀다보니 탑다운 재귀가 다 비슷한거같기도 하고?.. 종만북 피셜 더 직관적이라는게 팩트인듯. 아 빨리 플레찍고 종만북 달리기 해야징~