백준17825: 주사위 윷놀이

주사위 윷놀이 성공

 

 

 

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

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 복사

190

예제 입력 2 복사

 

1 1 1 1 1 1 1 1 1 1

예제 출력 2 복사

133

예제 입력 3 복사

5 1 2 3 4 5 5 3 2 4

예제 출력 3 복사

214

예제 입력 4 복사

5 5 5 5 5 5 5 5 5 5

예제 출력 4 복사

130

출처

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

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 시뮬레이션
• 백트래킹

문제 - 1 페이지

 

 

#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부터 꽤 어려운것 같다.. 힘내서 이 구간을 뚫어보자!