주사위 윷놀이 성공

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

512 MB

10054

4112

2490

37.359%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

1 2 3 4 1 2 3 4 1 2

예제 출력 1 복사

예제 입력 2 복사

1 1 1 1 1 1 1 1 1 1

예제 출력 2 복사

예제 입력 3 복사

5 1 2 3 4 5 5 3 2 4

예제 출력 3 복사

예제 입력 4 복사

5 5 5 5 5 5 5 5 5 5

예제 출력 4 복사

출처

문제를 만든 사람: baekjoon
문제를 다시 작성한 사람: jh05013

알고리즘 분류

문제 - 1 페이지

www.acmicpc.net

#include<iostream>
#include<algorithm>
using namespace std;
int order[10];
int mal[4];
int map[35];
int turn[35];
bool check[35];
int score[35];
int answer;
void dfs(int cnt, int sum) {
    if (cnt == 10) {
        answer = max(answer, sum);
        return;
    }
    for (int i = 0; i < 4; i++) {
        int prev = mal[i];
        int now = prev;
        int move = order[cnt];

        if (turn[now] > 0) {
            now = turn[now];
            move -= 1;
        }

        while (move--) {
            now = map[now];
        }

        if (now != 21 && check[now] == true) continue;

        check[prev] = false;
        check[now] = true;
        mal[i] = now;

        dfs(cnt + 1, sum + score[now]);

        mal[i] = prev;
        check[prev] = true;
        check[now] = false;
    }
}

int main() {
    for (int i = 0; i < 21; i++) map[i] = i + 1;//맵의 u자 곡선
    for (int i = 22; i < 27; i++) map[i] = i + 1;//I선

    map[21] = 21;
    map[28] = 29; map[29] = 30; map[30] = 25;
    map[31] = 32; map[32] = 25; map[27] = 20;



    turn[5] = 22;//좌에서 꺽임 
    turn[15] = 28;//우에서 꺽임
    turn[10] = 31;//U의 맨밑점에서 위로 꺽임
    turn[25] = 26;//U의 중간지점에서 위로 꺽임
      
    
    for (int i = 0; i < 21; i++) score[i] = i * 2;
    score[22] = 13; score[23] = 16; score[24] = 19;//---25
    score[28] = 28; score[29] = 27; score[30] = 26;//25---
    score[31] = 22; score[32] = 24;//|선 위 
    score[26] = 30; score[27] = 35;//|선 아래
    score[25] = 25;

    // 주사위 입력 받기.
    for (int i = 0; i < 10; i++) cin >> order[i];

    dfs(0, 0);

    cout << answer << "\n";


    return 0;
}

골드2부터 꽤 어려운것 같다.. 힘내서 이 구간을 뚫어보자!