[ALGORITHM] 백준 17825 - 주사위 윷놀이

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

17825번: 주사위 윷놀이

문제

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

• 처음에는 시작 칸에 말 4개가 있다.
• 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
• 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
• 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
• 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

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

입력

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

출력

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

생각해보기

1. 10에서의 이동
   • 10 -> 13 -> 16 -> 19 -> 25
2. 20에서의 이동
   • 20 -> 22 -> 24 -> 25
3. 30에서의 이동
   • 30 -> 28 -> 27 -> 26 -> 25
4. 25 가운데 에서의 이동
   • 25 -> 30 -> 35 -> 40 -> 탈출
5.  탈출처리를 어떻게 할 것인가
6. 가운데 맵에서의 30이 겹치는 것과 26이 겹치는 것을 어떻게 처리하는가

코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int arr[10];
int ret=0;

bool chks(vector<int> v){
    for(int i=0;i<4;i++){
        if(v[i]==9999||v[i]==0)
            continue;
        for(int j=i+1;j<4;j++){
            if(v[i]==v[j])
                return false;
        }
    }
    return true;
}

pair<int,int> calc(int f, int d){
    int s=0;
    if(f>=100){
        while(d--){
            if(f==100||f==130||f==160)
                f+=30;
            else if(f==190||f==260||f==240)
                f=2500;
            else if(f==200||f==220)
                f+=20;
            else if(f==300)
                f=280;
            else if(f==280||f==270)
                f-=10;
            else if(f==2500||f==3000||f==3500)
                f+=500;
            else{
                f=9999;  
                break;
            }                  
        }
    }
    else{
        f+=2*d;
    }

    if(f==10||f==20||f==30)
        f*=10;
    else if(f==40)
        f=4000;

    if(f<100&&f>40)
        f=9999;
    
    if(f==9999)
        s=0;
    else if(f<100)
        s=f;
    else if(f<1000)
        s=f/10;
    else
        s=f/100;

    
    return {f,s};
}   

void dfs(vector<int> v, int d, int s){
    if(d==10){
        /*
        if(ret<s){
            cout<<'\n'<<s<<'\n';
            for(int i=0;i<4;i++)
                cout<<v[i]<<" ";
            cout<<'\n';
        }*/
        ret=max(ret,s);
        return;
    }

    for(int idx=0;idx<4;idx++){
        if(v[idx]==9999)
            continue;
        pair<int,int> p = calc(v[idx],arr[d]);
        vector<int> t = {v.begin(),v.end()};
        t[idx]=p.first;

        if(chks(t))
            dfs(t,d+1,s+p.second);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i=0;i<10;i++)
        cin>>arr[i];

    vector<int> v(5,0);
    
    dfs(v,0,0);
    cout<<ret<<'\n';

    return 0;
}