JUNGOL 실력키우기 1147 : 주사위 쌓기

보관함 2018. 12. 8. 10:20

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위 처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되는 것은 아니다.

주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, ... 의 순서로 쌓는 것이다. 쌓을 때는 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각 기둥이 된다. 이 사각 기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최대값을 구하는 프로그램을 작성하시오.

첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 주사위의 전개도에서 A, B, C, D, E, F 의 순서로 입력된다. 입력되는 숫자 사이에는 빈 칸이 하나씩 있다. 주사위의 개수는 10,000개 이하이며, 종류가 같은 주사위도 있을 수 있다.

한 옆면의 숫자의 합이 가장 큰 값을 출력한다.

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

입력 예의 주사위들을 쌓아서 출력 예와 같은 합을 얻으려면 아래 그림과 같이 쌓으면 된다.

주사위를 쌓은 뒤 4개의 옆 면의 중 하나의 합이 가장 큰 것을 구하는 문제입니다. 문제 자체는 상당히 어려워 보이는데 규칙을 보면 힌트가 있습니다.

바로 아래에 있는 주사위의 윗 면과 위에 놓을 주사위의 아랫면의 숫자가 같아야 한다는 것인데

이것을 통해 1층에 놓을 주사위의 윗면을 정하면 나머지 주사위를 놓는 방법은 정해지는 것을 알 수 있습니다.

그리고 최대 270도 까지 회전할 수 있다고 하는데 이것은 실행 함수에서 4번의 재귀를 처리해야 한다는 말하는 것 입니다.

그러므로 전체 구조는 함수 외부에서 윗면이 될 부분을 결정하는 반복문을 돌린다 -> 반복문 내에서는 재귀함수를 호출한다 -> 재귀함수에서 각 옆면에 대한 재귀를 처리한다 가 될 것 같습니다.

그런데 생각보다 시간이 오래걸렸네요. 아마 재귀함수에서 처리하는 재귀의 양이 많아서라고 생각됩니다.

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
#include <iostream>
#include <map>
#include <vector>
#include <array>
 
using namespace std;
using DICES = vector<array<int, 6>>;
 
// 윗면과 아랫면을 찾기위한 맵
enum shapeOrder { A = 0, B, C, D, E, F };
map<int, int> oppositSide{
    {A, F}, {B, D}, {C, E}, {D, B}, {E, C}, {F, A} 
};
 
int FindMaxDicesSide(DICES& dices, int upperSide, int stage = 0);
 
int main()
{
    int n;
    cin >> n;
 
    // 주사위를 저장할 벡터
    DICES dices(n);
    for (int i = 0; i < n; ++i)
    {
        // 각 주사위의 숫자 입력
        cin >> dices[i].at(A) >> dices[i].at(B)
            >> dices[i].at(C) >> dices[i].at(D)
            >> dices[i].at(E) >> dices[i].at(F);
    }
 
    // 6면에 대해 재귀적으로 반복하며 최대 합을 찾는다.
    int maxSum{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        int maxTemp{ FindMaxDicesSide(dices, dices[0].at(i)) };
        maxSum = (maxTemp > maxSum) ? maxTemp : maxSum;
    }
 
    cout << maxSum << endl;
}
 
int FindMaxDicesSide(DICES & dices, int upperSide, int stage)
{
    // 주사위를 다 쌓은 경우
    if (stage == dices.size()) return 0;
 
    // 들어온 값을 이용해 윗면과 아랫면의 인덱스를 구한다.
    int downIndex{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        if (dices[stage].at(i) == upperSide)
        {
            downIndex = i;
            break;
        }
    }
 
    int maxSum{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        // 위와 아랫면을 제외한 면의 합을 처리한다.
        if (i == downIndex || i == oppositSide[downIndex]) continue;
        int maxTemp{ dices[stage].at(i) 
            + FindMaxDicesSide(dices, dices[stage].at(oppositSide[downIndex]), stage + 1) };
        maxSum = (maxTemp > maxSum) ? maxTemp : maxSum;
    }
 
    return maxSum;
}
Colored by Color Scripter
cs

지금 처리한 방법은 모든 루트를 전부 확인하는 것인데 1층 주사위에서 모든 윗면을 처리하고 모든 방향에서 나올 수 있는 모든 합을 찾았는데

당연하게도 주사위의 개수가 10,000개 까지 등장하기 때문에 재시간에 끝낼수는 없었습니다.

다시 생각하면 결국 최댓값을 더하면 최대의 합이 구해질 것이므로 옆면 중 가장 큰 값을 찾아 그 값에 대해서만 재귀적으로 처리하면 유효시간 내에 최댓값을 찾을 수 있을 것 같습니다.

일단 속도는 유효하게 향상시킬 수 있었습니다. 그런데 정답을 찾지는 못 한것 같습니다. 주사위는 모든 면을 회전해서 둘 수 있으니까 옆면에서 가장 큰 값만 찾으면 당연하게 최댓값을 찾을 수 있다고 생각했는데 어디선가 잘못된 부분이 있었던 것 같습니다.

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
#include <iostream>
#include <map>
#include <vector>
#include <array>
 
using namespace std;
using DICES = vector<array<int, 6>>;
 
// 윗면과 아랫면을 찾기위한 맵
enum shapeOrder { A = 0, B, C, D, E, F };
map<int, int> oppositSide{
    {A, F}, {B, D}, {C, E}, {D, B}, {E, C}, {F, A} 
};
 
int FindMaxDicesSide(DICES& dices, int upperSide, int stage = 0);
 
int main()
{
    int n;
    cin >> n;
 
    // 주사위를 저장할 벡터
    DICES dices(n);
    for (int i = 0; i < n; ++i)
    {
        // 각 주사위의 숫자 입력
        cin >> dices[i].at(A) >> dices[i].at(B)
            >> dices[i].at(C) >> dices[i].at(D)
            >> dices[i].at(E) >> dices[i].at(F);
    }
 
    // 6면에 대해 재귀적으로 반복하며 최대 합을 찾는다.
    int maxSum{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        int maxTemp{ FindMaxDicesSide(dices, dices[0].at(i)) };
        maxSum = (maxTemp > maxSum) ? maxTemp : maxSum;
    }
 
    cout << maxSum << endl;
}
 
int FindMaxDicesSide(DICES & dices, int upperSide, int stage)
{
    // 주사위를 다 쌓은 경우
    if (stage == dices.size()) return 0;
 
    // 들어온 값을 이용해 윗면의 인덱스를 찾는다.
    int downIndex{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        if (dices[stage].at(i) == upperSide)
        {
            downIndex = i;
            break;
        }
    }
 
    // 옆면 중 가장 큰 값을가진 인덱스를 찾는다.
    int maxValueIndex{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        if (i == downIndex || i == oppositSide[downIndex]) continue;
        if (dices[stage].at(i) > dices[stage].at(maxValueIndex))
        {
            maxValueIndex = i;
        }
    }
 
    return dices[stage].at(maxValueIndex)
        + FindMaxDicesSide(dices, dices[stage].at(oppositSide[downIndex]), stage + 1);
}
Colored by Color Scripter
cs

일단 왜 결과가 달라졌는지 확인해 봐야할 것 같습니다. 실행 중간 결과를 뽑으면 다음과 같습니다.

일단 58이 나오는 것은 처음 부분만 존재하고 나머지는 57, 56으로 나왔습니다.

그런데 중간에 최댓값에서 제외됐어야 할 Down인덱스의 값이 최댓값으로 설정된 경우가 발생했습니다.

이 최댓값을 찾는 부분에서 문제가 발생한 것으로 보입니다.

코드를 다시 분석해 보니 최댓값 인덱스를 찾을 때 최초 인덱스를 0으로 두고 시작해서 그보다 큰 값이 나올 수 없기 때문에 위와 같은 문제가 발생한 것으로 보입니다. 그러므로 최초 인덱스를 윗면, 아랫면이 아닌 값으로 설정하면 문제가 해결 될 것 같네요.

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
#include <iostream>
#include <map>
#include <vector>
#include <array>
 
using namespace std;
using DICES = vector<array<int, 6>>;
 
// 윗면과 아랫면을 찾기위한 맵
enum ShapeOrder { A = 0, B, C, D, E, F };
map<int, int> oppositSide{
    {A, F}, {B, D}, {C, E}, {D, B}, {E, C}, {F, A} 
};
 
int FindMaxDicesSide(DICES& dices, int upperSide, int stage = 0);
 
int main()
{
    int n;
    cin >> n;
 
    // 주사위를 저장할 벡터
    DICES dices(n);
    for (int i = 0; i < n; ++i)
    {
        // 각 주사위의 숫자 입력
        cin >> dices[i].at(A) >> dices[i].at(B)
            >> dices[i].at(C) >> dices[i].at(D)
            >> dices[i].at(E) >> dices[i].at(F);
    }
 
    // 6면에 대해 재귀적으로 반복하며 최대 합을 찾는다.
    int maxSum{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        int maxTemp{ FindMaxDicesSide(dices, dices[0].at(i)) };
        maxSum = (maxTemp > maxSum) ? maxTemp : maxSum;
    }
 
    cout << maxSum << endl;
}
 
int FindMaxDicesSide(DICES & dices, int upperSide, int stage)
{
    // 주사위를 다 쌓은 경우
    if (stage == dices.size()) return 0;
 
    // 들어온 값을 이용해 윗면의 인덱스를 찾는다.
    int upIndex{ 0 }, downIndex{ 0 };
    for (int i = 0; i < 6; ++i)
    {
        if (dices[stage].at(i) == upperSide)
        {
            downIndex = i;
            upIndex = oppositSide[downIndex];
            break;
        }
    }
 
    // 옆면 중 가장 큰 값을가진 인덱스를 찾는다.
    int maxValueIndex{ (upIndex == 0 || downIndex == 0) ? 1 : 0 };
    for (int i = maxValueIndex + 1; i < 6; ++i)
    {
        if (i == upIndex || i == downIndex) continue;
        if (dices[stage].at(i) > dices[stage].at(maxValueIndex))
        {
            maxValueIndex = i;
        }
    }
 
    return dices[stage].at(maxValueIndex) + FindMaxDicesSide(dices, dices[stage].at(upIndex), stage + 1);
}
Colored by Color Scripter
cs

JUNGOL) 문제은행) 실력키우기) 주사위 쌓기

저작자표시 비영리 변경금지

ABOUT ME

무제 무제

티스토리툴바

ABOUT ME

관련글 관련글 더보기

티스토리툴바