[BOJ] 17825. 주사위 윷놀이 - 중복순열

[BOJ] 17825. 주사위 윷놀이 - 중복순열

제출일 : 2019-11-11

문제 풀이 시간 : 5H

난이도 : ★★★★☆

Problem

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

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

가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다.

게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에는 그 칸으로 이동할 수 없다. 시작과 도착칸은 말이 이미 있어도 이동할 수 있다. 말이 이동을 마칠때마다 칸에 적혀있는 수가 점수에 추가된다.

말이 도착으로 이미 이동한 경우에는 더 이상 이동할 수 없고, 말이 이동하려고 하는 칸이 도착을 넘어가는 경우에는 도착에서 이동을 마친다.

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

Input

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

Output

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

Example

input

1 2 3 4 1 2 3 4 1 2

output

190

Solution & Inpression

삼성 SW 역량 테스트 기출 문제

움직일수 있는 길은 4가지 경우로

모든 경우의 수($4^{10}=1,048,576$)를 중복순열을 이용하여 구한뒤 중복되는 경우는 버리고 최대값을 구하여 해결하였다.

중복되는 경우의 수가 일반적인 경우에는 움직이고 있는길과 현재 위치가 같을 경우이지만

마지막 25, 30, 34, 40은 움직이는 길이 다르더라도 같은 위치일 수 있다

이경우는 하드코딩으로 예외처리를 하였다.

이 문제를 풀며 난관에 여러번 부딛혔는다.

1. 문제를 이해하는데 많은 시간이 소요되었고
2. 중복을 처리할때 같은 경로가 아니더라도 같은 위치일 수 있고
3. 중복되는 경우는 제외해야 한다.

위 3가지를 고려했다면 더 빠른 시간내에 해결 할 수 있지 않았을까??

Code

언어 : JAVA

메모리 : 158,884 kb

실행시간 : 1,124 ms

import java.util.Scanner;

public class Main {
    static int[] route0 = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40 };
    static int[] route1 = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 28, 27, 26, 25, 30, 35, 40 };
    static int[] route2 = { 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 25, 30, 35, 40 };
    static int[] route3 = { 0, 2, 4, 6, 8, 10, 13, 16, 19, 25, 30, 35, 40 };

    static int[] cmd;
    static int[] move;
    static int[][] horse;

    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        cmd = new int[10];
        for (int i = 0; i < 10; i++) { // 입력되는 명령어의 수 10개
            cmd[i] = sc.nextInt();
        }
        sc.close();
        // 입력 끝

        move = new int[10];
        max = Integer.MIN_VALUE;
        DFS(0);
        System.out.println(max);
    }

    private static void DFS(int depth) {
        if (depth == cmd.length) {
            int sum = solve();
            if (max < sum)
                max = sum;
            return;
        }

        for (int i = 0; i < 4; i++) {
            move[depth] = i;
            DFS(depth + 1);
        }

    }

    private static int solve() {
        horse = new int[4][2]; // 말의 위치, 가는 길, 움직인 횟수
        int sum = 0;

        for (int i = 0; i < 10; i++) {
            int cur = move[i]; // 현재움직일 말의 번호.
            horse[cur][0] += cmd[i]; // 움직였을때의 위치.
            int tmp = horse[cur][1];

            // ================길 변경================
            if (horse[cur][1] == 0) {
                if (horse[cur][0] == 5)
                    horse[cur][1] = 3;
                else if (horse[cur][0] == 10)
                    horse[cur][1] = 2;
                else if (horse[cur][0] == 15)
                    horse[cur][1] = 1;
            }

            // ================중복체크================
            boolean flag = false;
            int j = 0;
            for (; j < horse.length; j++) {
                if (cur != j) {
                    if (horse[cur][0] == horse[j][0] && horse[cur][1] == horse[j][1]) {
                        flag = true;
                        break;
                    } else if ((horse[cur][1] == 1 && horse[cur][0] == 19) || (horse[cur][1] == 2 && horse[cur][0] == 13)
                            || (horse[cur][1] == 3 && horse[cur][0] == 9)) {
                        // 25번에 도착했을때
                        if (horse[j][1] == 1 && horse[j][0] == 19) {// 1번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 2 && horse[j][0] == 13) {// 2번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 3 && horse[j][0] == 9) {// 3번길에 같은위치
                            flag = true;
                            break;
                        }
                    } else if ((horse[cur][1] == 1 && horse[cur][0] == 20) || (horse[cur][1] == 2 && horse[cur][0] == 14)
                            || (horse[cur][1] == 3 && horse[cur][0] == 10)) {
                        // 30번에 도착했을때
                        if (horse[j][1] == 1 && horse[j][0] == 20) {// 1번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 2 && horse[j][0] == 14) {// 2번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 3 && horse[j][0] == 10) {// 3번길에 같은위치
                            flag = true;
                            break;
                        }
                    }

                    else if ((horse[cur][1] == 1 && horse[cur][0] == 21) || (horse[cur][1] == 2 && horse[cur][0] == 15)
                            || (horse[cur][1] == 3 && horse[cur][0] == 11)) {
                        // 35번에 도착했을때
                        if (horse[j][1] == 1 && horse[j][0] == 21) {// 1번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 2 && horse[j][0] == 15) {// 2번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 3 && horse[j][0] == 11) {// 3번길에 같은위치
                            flag = true;
                            break;
                        }
                    } else if ((horse[cur][1] == 0 && horse[cur][0] == 20) || (horse[cur][1] == 1 && horse[cur][0] == 22)
                            || (horse[cur][1] == 2 && horse[cur][0] == 16) || (horse[cur][1] == 3 && horse[cur][0] == 12)) {
                        // 40번에 도착했을때
                        if (horse[j][1] == 0 && horse[j][0] == 20) {// 0번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 1 && horse[j][0] == 22) {// 1번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 2 && horse[j][0] == 16) {// 2번길에 같은위치
                            flag = true;
                            break;
                        } else if (horse[j][1] == 3 && horse[j][0] == 12) {// 3번길에 같은위치
                            flag = true;
                            break;
                        }
                    }
                }
            }
            if (flag) {
                return Integer.MIN_VALUE;
            }

            // ================더하기================
            if (horse[cur][1] == 0 && horse[cur][0] < route0.length)
                sum += route0[horse[cur][0]];
            else if (horse[cur][1] == 1 && horse[cur][0] < route1.length)
                sum += route1[horse[cur][0]];
            else if (horse[cur][1] == 2 && horse[cur][0] < route2.length)
                sum += route2[horse[cur][0]];
            else if (horse[cur][1] == 3 && horse[cur][0] < route3.length)
                sum += route3[horse[cur][0]];
        }
        return sum;
    }

}