[BOJ] 17825 주사위 윷놀이

 

 

[문제]

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

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int[] board = {
			0,2,4,6,8,10,12,14,16,18,20,
			22,24,26,28,30,32,34,36,38,40,
			13,16,19,22,24,28,27,26,25,30,
			35,0
	};
	static int[] dices,locs,spacial,nxt;
	static int result = 0;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		dices = new int[10];
		for(int i=0;i<10;i++) {
			dices[i] = Integer.parseInt(st.nextToken());
		}
		locs = new int[4];
		
		spacial = new int[33];
		nxt = new int[33];
		for(int i=0;i<32;i++) nxt[i] = i+1;
		nxt[23] = nxt[25] = 29;
		nxt[31] = 20;
		nxt[20] = 32;
		spacial[5] = 21;
		spacial[10] = 24;
		spacial[15] = 26;
		dfs(0,0);
		System.out.println(result);
	}
	private static void dfs(int idx,int sum) {
		if(idx==10) {
			result = Math.max(result, sum);
			return;
		}
		int dice = dices[idx];
		for(int i=0;i<4;i++) {
			int loc = locs[i];
			if(loc==32) continue;
			int tempLoc = loc;
			for(int j=0;j<dice;j++) {
				if(tempLoc==32) break;
				if(j==0 && spacial[tempLoc]!=0) tempLoc = spacial[tempLoc];
				else tempLoc = nxt[tempLoc];
			}
			boolean collision = false;
			if(tempLoc!=32) {
				for(int j=0;j<4;j++) {
					if(i!=j && locs[j]==tempLoc) {
						collision = true;
						break;
					}
				}
			}
			if(!collision) {
				locs[i] = tempLoc;
				dfs(idx+1,sum+board[tempLoc]);
				locs[i] = loc;
			}
		}
	}
}