백준 2116. 주사위 쌓기
구현 문제
이전에 푼 주사위 굴리기문제와 유사한 문제인줄 알고 도전했으나
전혀 상관없는 구현 문제였음
문제 분석
주사위를 쌓는다
주사위의 눈에는 1-6 숫자가 하나씩 적혀있다
일반적인 주사위처럼 반드시 마주보는 면의 합이 7이 되지는 않음
아래에서 부터 1번 주사위, 2번 주사위 , … 순서로 쌓는다
서로 붙어있는 두개의 주사위에서, 아래에 있는 주사위의 윗면에 적혀있는 숫자는
위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다.
다시 말해서, 1면 주사위의 윗면의 숫자는, 2면 주사위의 아랫면의 숫자와 같아야함
단, 1번 주사위는 마음대로 놓을 수 있다.
이렇게 쌓아 놓으면 긴 사각기둥이 되는데, 이 사각 기둥에는 4개의 긴 옆면이 있다.
이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓는다.
이 때 이 최대값을 구하는 문제
입력
첫줄에 주사위의 개수가 입력
그 다음줄 부터 한줄에 하나씩 주사위의 종류가 1번 주사위 부터 번호 순서대로 입력됨
주사위의 종류는 각 면에 적혀진 숫자가 그림 1에 있는 주사위의 전개도에서 A,B,C,D,E,F의 순서로 입력된다
입력되는 숫자 사이에는 빈 칸이 하나씩 있다
주사위의 개수는 10,000개 이하이며, 종류가 같은 주사위가 있을 수 있음
출력
첫 줄에 한 옆면의 숫자의 합이 가장 큰 값을 출력한다
예제 분석
1)
1
2
3
4
5
6
5
2 3 1 6 5 4
3 1 2 4 6 5
5 6 4 1 3 2
1 3 6 2 4 5
4 1 6 5 2 3
5개 주사위가 주어진다
첫번째 주사위 2 3 1 6 5 4는 마음대로 놓을 수 있으므로, A-F까지 6개 면 중 아무면이나 바닥에 놓아본다
A면이 바닥에 오는 경우)
1
2
3
4
5
주사위 1 : 2가 바닥에 오면 4(F)가 위로 간다. 옆면에는 3, 1, 6, 5가 오는데, 90도, 180도, 270도 맘대로 돌릴 수 있으므로 6이 오게 배치한다
주사위 2 : 4가 바닥으로 가야한다. 마주보는 면인 1이 위로 가면, 옆면은 3, 2, 6, 5가 옆으로 온다. 마찬가지로 6이 오도록 배치
주사위 3 : 1이 바닥, 마주보는 면 6이 위, 옆면은 {5, 4, 3, 2} 중 5
주사위 4 : ↓ : 6 , ↑ : 1, ←→ : {3, 2, 4, 5} => 5
주사위 5 : ↓ : 1 , ↑ : 5, ←→ : {4, 6, 2, 3} => 6
옆면의 총 합은 6+6+5+5+6 = 28이다
B면)
1
2
3
4
5
주사위 1: ↓ : 3 , ↑ : 6, ←→ : {2,1,5,4} => 5
주사위 2: ↓ : 6 , ↑ : 2, ←→ : {3,1,4,5} => 5
주사위 3: ↓ : 2 , ↑ : 5, ←→ : {6,4,1,3} => 6
주사위 4: ↓ : 5 , ↑ : 1, ←→ : {3,6,2,4} => 6
주사위 5: ↓ : 1 , ↑ : 5, ←→ : {4,6,2,3} => 6
옆면의 총 합 28
…
E면)
1
2
3
4
5
주사위 1: ↓ : 5 , ↑ : 1, ←→ : {2,3,6,4} => 6
주사위 2: ↓ : 1 , ↑ : 4, ←→ : {3,2,6,5} => 6
주사위 3: ↓ : 4 , ↑ : 3, ←→ : {5,6,3,2} => 6
주사위 4: ↓ : 3 , ↑ : 2, ←→ : {1,6,4,5} => 6
주사위 5: ↓ : 2 , ↑ : 6, ←→ : {4,1,5,3} => 5
…
모든 면을 다 테스트해보면 29가 최대값이 나온다
알고리즘
처음 보고 문제와 유사하거나 DFS 문제인줄 알았으나 아니였다
주사위를 굴릴 필요가 없기 때문
처음 놓는 주사위의 면에 따라 연달아 주사위들의 윗면과 아랫면이 고정되기 때문에
놓은 주사위들 중 옆면의 최대값만 찾아서 더해주고 다음 주사위의 옆면을 구하면 된다
O(6면 * 10000개 * 4개중 최대값 찾기)
1
2
3
4
5
6
7
8
9
10
11
12
1. 전처리
- N 입력받기
- N개의 주사위의 각 면 입력받기
2. 첫번째 주사위의 6개 면 중 하나를 골라 아랫면에 배치한다
- 첫번째 아랫면과 마주보는 윗면의 수를 찾는다
- 옆면의 최대값을 찾아 결과값에 더한다
- 두번째 주사위부터 해당 작업을 N번째 주사위까지 반복한다
- 이전에 구한 윗면의 수를 바닥으로 놓는다
- 옆면의 최대값을 찾아 결과값에 더한다
- 바닥에 놓은 수와 마주보는 수를 구한다. 다음 수의 아랫면이다
- 결과값을 기존값과 비교, 갱신
3. 결과 출력
주사위의 마주보는 면을 구하는 방법은 그림을 보면
A<->F, B<->D, C<->E 로 되어있다
이를 dice[6] = {A, B, C, D, E, F} 라고 하면
1
2
3
dice[0] <=> dice[5]
dice[1] <=> dice[3]
dice[2] <=> dice[4]
이므로
opposite[6] = { 5, 3, 4, 1, 2, 0 } 로 표현할 수 있다
소스코드
```cpp #include
using namespace std;
int N; vector< vector
int opposite[6] = { 5, 3, 4, 1, 2, 0 };
void Input() { // freopen(“input.txt”, “r”, stdin); cin » N; dice.resize(N); for (int i = 0; i < N; i++) { dice[i].resize(6); for (int j = 0; j < 6; j++) { cin » dice[i][j]; } } }
int main() { Input();
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
// 첫번째 주사위의 6면
int max_val = 0;
for (int first_dice = 0; first_dice < 6; first_dice++) {
// 첫번째 주사위 처리
int current_bottom_val = dice[0][first_dice];
int current_top_val = dice[0][opposite[first_dice]]; // 반대면의 수 구하기
int cur_max = 0;
for (int side = 0; side < 6; side++) {
if (dice[0][side] == current_bottom_val || dice[0][side] == current_top_val) continue;
cur_max = std::max(cur_max, dice[0][side]);
}
// 2번쨰~N번째 주사위 처리
for (int i = 1; i < N; i++) {
// top_side에 이전 주사위의 윗면이 기록되어 있음 -> 해당 숫자가 이번 주사위 아랫면이 되어야함
// i번째 주사위의 j면의 숫자가 top_side와 같은지 체크
current_bottom_val = current_top_val;
// 현재 주사위에서 아랫면의 인덱스 찾기
int bottom_idx = -1;
for (int j = 0; j < 6; j++) {
if (dice[i][j] == current_bottom_val) {
bottom_idx = j;
break;
}
}
// 윗면의 값 구하기
current_top_val = dice[i][opposite[bottom_idx]];
// 옆면에서 최대값을 찾는다
int side_max = 0;
for (int j = 0; j < 6; j++) {
if (dice[i][j] == current_bottom_val || dice[i][j] == current_top_val) continue; // 윗면이나 아랫면 패스
side_max = std::max(side_max, dice[i][j]);
}
cur_max += side_max;
}
max_val = std::max(max_val, cur_max);
}
cout << max_val;
return 0; } */