말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.
주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.
/** * created by victory_woo on 2020/04/15 */ publicclasssw17825Re{ privatestaticfinalint TEN = 10; privatestaticint[] permutation, now, step; privatestaticboolean[] check; privatestatic Node[] map; privatestaticint max;
publicstaticvoidmain(String[] args)throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] in = br.readLine().split(" ");
permutation = newint[TEN]; step = newint[TEN]; map = new Node[43];
for (int i = 0; i < TEN; i++) step[i] = toInt(in[i]); setDice(); getPermutation(0); System.out.println(max); }
// 파란 점이 있는 부분에 대해서 처리한다. // 바깥 라인과의 중복된 값이 존재하기 때문에 인덱스를 다르게 주었고, 값은 그대로 저장했다. // 또한, 빨간 점으로 된 다음 좌표를 저장한다. privatestaticvoidsetDice(){ for (int i = 0; i <= 40; i += 2) map[i] = new Node(i, i + 2);
map[11] = new Node(13, 13); map[13] = new Node(16, 15); map[15] = new Node(19, 25);
map[17] = new Node(22, 19); map[19] = new Node(24, 25);
map[31] = new Node(28, 33); map[33] = new Node(27, 35); map[35] = new Node(26, 25);
map[25] = new Node(25, 37);
map[37] = new Node(30, 39); map[39] = new Node(35, 40);
map[42] = new Node(0, 42); }
privatestaticvoidgetPermutation(int depth){ if (depth == 10) { now = newint[4]; check = newboolean[43]; move(); return; }
for (int i = 0; i < 4; i++) { permutation[depth] = i; getPermutation(depth + 1); } }
privatestaticvoidmove(){ int score = 0; for (int i = 0; i < TEN; i++) { // 말을 움직여서 말이 도착한 지점의 값을 구한다. // 말이 step 만큼 움직이도록 horseMove() 함수를 호출한다. // end 값은 말이 주사위 step 만큼 움직이고 난 뒤의 칸. int end = horseMove(permutation[i], step[i]); if (end == -1) return; now[permutation[i]] = end; // 현재 말이 있는 칸을 업데이트 한다. score += map[end].score; }
if (max < score) max = score; }
// now : 윷놀이 판 위에서 말이 위치한 인덱스.(말이 있는 윷놀이 판의 인덱스) privatestaticinthorseMove(int horse, int step){ // 몇 번째 말이 움직일 것인지 뽑는다. // 즉, 이동할 말을 정한다. int temp = now[horse];
// 말이 step 만큼 움직인다. // 첫 좌표이면서 파란 점이라면 파란 점을 temp 에 저장한다. // 그게 아니라면 말이 이동할 다음 좌표(빨간 점의 위치)를 찾아 temp 에 저장한다. for (int i = 0; i < step; i++) { if (i == 0 && map[temp].isBlue) { temp = map[temp].blue; continue; }
temp = map[temp].red; }
// 도착 지점에 도착하지도 않았는데, 방문한 곳을 또 방문한 경우. if (temp <= 40 && check[temp]) { return -1; } else { check[now[horse]] = false; check[temp] = true; return temp; } }