백준 17825번 : 주사위 윷놀이 (c++)

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

17825번: 주사위 윷놀이

문제
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

• 처음에는 시작 칸에 말 4개가 있다.

• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.

• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.

• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.

• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력
첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력
얻을 수 있는 점수의 최댓값을 출력한다.

예제 입력
1 2 3 4 1 2 3 4 1 2

예제 출력
190

#include <iostream>
#include <algorithm>

using namespace std;

int num[10];
int answer =0;
int position[4]={0,};
bool exChk[34]={false,};

int move(int np, bool chking){
    if(np==5&&chking) return 26;
    else if(np==10&&chking) return 21;
    else if(np==15&&chking) return 29;
    else if(np==20) return 33;
    else if(np==26) return 27;
    else if(np==27) return 28;
    else if(np==28) return 23;
    else if(np==29) return 30;
    else if(np==30) return 31;
    else if(np==31) return 23;
    else if(np==25) return 20;
    else if(np==33) return 33;
    else return np+1;
}
int score(int pos){
    if(pos==26) return 13;
    else if(pos==27) return 16;
    else if(pos==28) return 19;
    else if(pos==21) return 22;
    else if(pos==22) return 24;
    else if(pos==23) return 25;
    else if(pos==24) return 30;
    else if(pos==25) return 35;
    else if(pos==29) return 28;
    else if(pos==30) return 27;
    else if(pos==31) return 26;
    else if(pos==33) return 0;
    else return pos*2;
}
void dfs(int cnt, int total){
    if(cnt==10){
        answer = max(answer,total);
        return;
    }
    for(int i=0;i<4;i++){
        int start = position[i];
        int np = start;
        int dist = num[cnt];
        if(np==5||np==10||np==15){
            dist--;
            np = move(np, true);
        }
        while(dist--){
            np = move(np, false);
        }
        if(np!=33&&exChk[np]) continue;
        position[i] = np;
        exChk[start]=false;
        exChk[np]=true;
        dfs(cnt+1 , total+score(np));
        position[i] = start;
        exChk[start]=true;
        exChk[np]=false;
    }
}

int main(){

    freopen("input.txt","r",stdin);

    for(int i=0;i<10;i++){
        cin>>num[i];
    }
    dfs(0,0);
    cout<<answer;
    return 0;
}