코딩 공부/백준

[백준][C++] 2116 주사위 쌓기

김 정 환 2021. 3. 2. 22:56
반응형

www.acmicpc.net/problem/2116

 

2116번: 주사위 쌓기

첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는

www.acmicpc.net

 

 

 

알고리즘 종류

    - 구현

 

 

 

사고 과정

    - 주사위의 바닥면과 윗면과의 관계를 알야한다. 왜냐하면, 바닥면을 알면 윗면이 무슨 숫자와 index인지 알아야 다음 주사위를 동작시킬 수 있기 때문이다. 입력된 값을 분석해보면, 0-5, 1-3, 2-4 인덱스끼리 윗면과 아랫면 또는 아랫면과 윗면이 된다는 것을 알 수 있다.

    - 주사위 n개를 for문으로 순환한다.

    - 1번 주사위의 바닥면은 고른다. 마치 0번 주사위의 윗면을 고르는 것과 같다. 이렇게 계속 윗면을 비교할 것이다.

    - 2번 주사위의 바닥면을 1번 주사위의 윗면과 같은지 확인하고, 옆면의 최댓값을 구한다.

    - n번 반복한다.

 

 

구현(C++)

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
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int n;
int answer = 0;
vector<vector<int> > bag;
 
 
void stacking(){
    for(int i=0; i<6; i++){
        // 1번 주사위의 바닥에 붙은 번호 구하기 . 마치 0번 주사위의 윗면 번호 구하는 것과 같다. 
        int upper = bag[0][i];
        int sum = 0;
        
        // 주사위 1번부터 n번까지 순환  
        for(int j=0; j<n; j++){
            // 면 6개 확인하기  
            for(int k=0; k<6; k++){
                // 윗면과 같은 아랫면 찾기  
                if(bag[j][k] == upper){
                    // 0-5, 1-3, 2-4 번호로 윗면과 아랫면을 묶을 수 있다. 
                    if(k==0){
                        // 다음 주사위의 윗면 구하기  
                        upper = bag[j][5];
                        // 옆면에서 가장 큰 수 찾기  
                        sum += max(max(bag[j][1], bag[j][2]), max(bag[j][3], bag[j][4]));
                    }
                    else if(k==1){
                        upper = bag[j][3];
                        sum += max(max(bag[j][0], bag[j][2]), max(bag[j][4], bag[j][5]));
                    }
                    else if(k==2){
                        upper = bag[j][4];
                        sum += max(max(bag[j][0], bag[j][1]), max(bag[j][3], bag[j][5]));
                    }
                    else if(k==3){
                        upper = bag[j][1];
                        sum += max(max(bag[j][0], bag[j][2]), max(bag[j][4], bag[j][5]));
                    }
                    else if(k==4){
                        upper = bag[j][2];
                        sum += max(max(bag[j][0], bag[j][1]), max(bag[j][3], bag[j][5]));
                    }
                    else if(k==5){
                        upper = bag[j][0];
                        sum += max(max(bag[j][1], bag[j][2]), max(bag[j][3], bag[j][4]));
                    }
                    break;
                }
            }
        }
        if(sum > answer) answer = sum;
    }
}
 
 
void solution(){
    stacking();
    cout << answer << endl;
}
 
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    cin >> n;
    for(int i=0; i<n; i++){
        vector<int> v;
        
        int num;
        for(int j=0; j<6; j++){
            cin >> num;
            v.push_back(num);
        }
        bag.push_back(v);
    }
    
    solution();
}
 
 
cs

 

 

 

시행착오

    - 이 문제를 풀기 전에 Maaaaaaaaaze라는 문제를 풀고 왔었다. 이번 주사위 쌓기와 비슷하게 판을 쌓아서 회전하는 유형이었다. maze문제는 쌓는 것까지 조합으로 구해야하는 문제였다. maze를 풀고 주사위 쌓기 문제를 푸니, 나도 모르게 쌓는 순서를 조합으로 구하고 있었다. 그래서 왜 계속 테스트케이스에서 최댓값이 30으로 나오는지 의아했다. 제출하고 시간초과가 난 것을 보고, 문제를 잘못 읽었다는 생각을 했고 다시 읽어보니 주사위는 입력된 순서대로 쌓는 것이었다. 조합을 구할 필요가 없었다... 문제를 똑바로 읽는 꼼꼼한 태도를 다시 길러야겠다.

반응형