[Algorithm] 다이나믹프로그래밍 - BoardGame

#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
 
int T, N, K, M;
int Score[110], UseK[7], Total[7][7][7][7][7][7][7][7]; //Board Score판, 숫자카드 사용내역, DP배열([이전카드][현재카드][1번카드사용내역][2번카드사용내역]...[6번카드사용내역]
int Result;
 
int boardSearch(int before, int current, int kSum) {
    if (kSum >= N) { //말의 위치가 최종의 위치에 도달했을때 Return.
        Total[before][current][UseK[1]][UseK[2]][UseK[3]][UseK[4]][UseK[5]][UseK[6]] = Score[kSum - N];
        return Score[kSum - N];
    }
    for (int i = 1; i <= K; i++) { //current 카드에서 자식이 될 카드를 찾는다.
        if (i == current || UseK[i] == 0) continue; //현재 카드와 자식이 될 후보 카드가 동일한 숫자라면 자식이 될 수 없고, 사용가능한 카드를 다 썼다면 자식이 될 수 없다.
        int *pp2 = &Total[before][current][UseK[1]][UseK[2]][UseK[3]][UseK[4]][UseK[5]][UseK[6]];
        UseK[i]--;
        int *pp1 = &Total[current][i][UseK[1]][UseK[2]][UseK[3]][UseK[4]][UseK[5]][UseK[6]];
        if (*pp1 == -1) { //혹시나 내가 들어갈 자식카드가 동일 조건에 값이 존재한다면, 이것은 이미 최소값으로 계산되어 있기 때문에 Search하지 않는다.(그냥 DP배열에서 가져다 쓸뿐)
            *pp1 = boardSearch(current , i, kSum + i);
        }
        if (*pp2 != -1) *pp2 = *pp2 > *pp1 + Score[kSum] ? *pp1 + Score[kSum] : *pp2; //이렇게해서 1~K번까지의 자식카드를 검색해가면서 현재 카드의 최소값을 갱신해나간다. 
        else *pp2 = *pp1 + Score[kSum];
        UseK[i]++;
    }
}
 
int main() {
    scanf("%d", &T);
    for (int t = 1; t <= T; t++) {
        scanf("%d%d%d", &N, &K, &M);
        for (int i = 0; i < N; i++) {
            scanf("%d", &Score[i]);
        }
        memset(Total, -1, sizeof(Total));
        memset(UseK, 0, sizeof(UseK));
        for (int i = 1; i <= K; i++) { //카드배열 초기화 => 최초의 상태는 사용개수만큼 초기화
            UseK[i] = M;
        }
        for (int i = 1; i <= K; i++) { //1번 카드 ~ K번 카드
            int *p2 = &Total[0][0][UseK[1]][UseK[2]][UseK[3]][UseK[4]][UseK[5]][UseK[6]]; //최상Root DP => 이것은 결과값을 저장하는 용도
            UseK[i]--;
            int *p1 = &Total[0][i][UseK[1]][UseK[2]][UseK[3]][UseK[4]][UseK[5]][UseK[6]]; //Root의 자식 branch에 대한 DP배열
            if (*p1 == -1) {
                *p1 = boardSearch(0 ,i, i); //Root의 자식 Branch는 1번카드~K번카드까지로하여 조회... 이놈들중에 최소값은 존재한다.
            }
            if (*p2 != -1) *p2 = *p2 > *p1? *p1: *p2; //최소값이 존재하면 최소값으로 교체
            else *p2 = *p1; //값이 없으면, 우선 값을 넣어준다.
            UseK[i]++;
        }
        printf("#%d %d\n", t, Total[0][0][UseK[1]][UseK[2]][UseK[3]][UseK[4]][UseK[5]][UseK[6]]);
        memset(Score, 0, sizeof(Score));
    }
}