2116번: 주사위 쌓기
첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는
www.acmicpc.net
주사위를 순서대로 쌓는데 i번 주사위의 윗면의 숫자와 i + 1번 주사위의 아랫면 숫자가 같아야합니다.
우선 rlist에 반대편 인덱스를 모두 저장해줍니다.
그 다음 0 ~ 5번 인덱스가 밑면일 경우를 다 구해서 각각의 최댓값을 갱신시켜주면 됩니다.
i번이 맨밑 인덱스라고 하면 반대 인덱스인 rx를 가져올수 있고, 이 두개를 제외한 나머지 숫자 중 max값을 찾아서 다음 인덱스로 재귀를 돌려주시면 됩니다.
이때 재귀를 돌릴 때 유지하는 값은 인덱스, 위에있는 값 (맞춰야하는 값), 현재까지 주사위의 최대 합입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int list[10000][6], rlist[6];
int N, ans;
void init() {
rlist[0] = 5;
rlist[5] = 0;
rlist[1] = 3;
rlist[3] = 1;
rlist[2] = 4;
rlist[4] = 2;
}
void dfs(int idx, int value, int sum) {
if (idx == N) {
ans = max(ans, sum);
return;
}
for (int i = 0; i < 6; i++) {
if (list[idx][i] == value) {
int rx = rlist[i];
int max_value = 0;
for (int j = 0; j < 6; j++) {
if (j == i || j == rx) continue;
max_value = max(max_value, list[idx][j]);
}
dfs(idx + 1, list[idx][rx], sum + max_value);
break;
}
}
}
void func() {
for (int i = 0; i < 6; i++) {
int rx = rlist[i];
int max_value = 0;
for (int j = 0; j < 6; j++) {
if (j == i || j == rx) continue;
max_value = max(max_value, list[0][j]);
}
dfs(1, list[0][rx], max_value);
}
}
void input() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < 6; j++) cin >> list[i][j];
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
init();
input();
func();
cout << ans << '\n';
return 0;
}
|
cs |
'algorithm > Implementation' 카테고리의 다른 글
| boj 8320 직사각형을 만드는 방법 (0) | 2021.02.25 |
|---|---|
| boj 3985 롤 케이크 (0) | 2021.02.25 |
| boj 10163 색종이 (0) | 2021.02.24 |
| boj 20055 컨베이어 벨트 위의 로봇 (0) | 2021.02.23 |
| boj 2331 반복수열 (0) | 2021.02.23 |