🥇[백준, 2116] 주사위 쌓기 (Java)

 

문제 링크

https://www.acmicpc.net/problem/2116

2116번: 주사위 쌓기

 

난이도

 

시간제한

2초

 

문제

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 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

 

출력

29

 

---

문제 풀이 과정

 문제 이해하기

 

먼저 주사위 그림 1을 살펴보자.

A의 반대 편에는 F, B의 반대편에는 D, C의 반대편에는 E가 있다는 것을 알 수 있다.

즉, 짝을 맞춰보면 A-F, B-D, C-E이다.

 

❓매번 최선의 선택을 하면 과연 주사위 옆면의 숫자의 합의 최댓값을 구할 수 있을까?

답은 "아니다"이다.

 

그 이유는 첫 번째 주사위에서 아랫면으로 1, 즉 최소의 수를 선택했다고 해도 그와 짝인 수가 6으로 최대일 수 있기 때문이다.

따라서 첫 번째 주사위의 아랫면을 1부터 6까지 고정시켜 가며 해당 경우에 따른 옆 면의 최댓값을 구한 다음 그중 가장 큰 값을 구해야 한다.

 

입력값 저장하기

 

public class BOJ_2116 {
    static int[][] dice;
    static final int diceCount = 6;
    static int[] diceMatch = {5, 3, 4, 1, 2, 0};  // A-F, B-D, C-E

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        dice = new int[N][diceCount];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < diceCount; j++) {
                dice[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }
}

 

위에서 살펴봤던 A-F, B-D, C-E를 인덱스로 표현하면 0-5, 1-3, 2-4가 되어 dicMatch변수에 저장한다.

그 후 이중 for문을 돌면서 주사위의 정보를 dice변수에 저장한다.

 

 첫 번째 주사위의 아랫면을 1부터 6까지 고정시키며 해당 경우 살펴보기

 

int result = 0;

for (int i = 0; i < diceCount; i++) {
    int bottom = dice[0][i];
    ...

    for (int j = 1; j < N; j++) {
        ...
    }

    result = Math.max(totalMax, result);
}

 

for문을 돌며 첫 번째 주사위의 아랫면을 고정시킨다.

 

❓그다음으로는 어떤 일을 해야 할까?

1. 해당 주사위의 아랫면에 따른 다음 주사위의 아랫면의 index를 구한다.

2. 다음 주사위 아랫면의 index를 통해 해당 주사위의 윗면의 index와 아랫면의 index를 제외한 index를 살펴보며 최댓값을 구하여 옆면의 최댓값을 구한다.

 

즉, 첫 번째 주사위의 아랫면을 고정시키면 다음 조건에 따라 다음 주사위의 윗면과 아랫면은 정해지게 된다.

서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다.

 

또한 문제에 다음과 같이 위아래를 고정한 채 옆으로 돌릴 수 있다는 조건이 있으므로 매 주사위마다 윗면과 아랫면을 제외한 값 중 최댓값을 찾으며 더해주면 된다.

이렇게 하기 위하여 각 주사위를 위아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 

 

index+1번째 주사위 아랫면 숫자로 다음 주사위 아랫면 index 찾기

 

static int findNextBottomIndex(int index, int bottom) {
    int nBottomIndex = 0;

    for (int i = 0; i < diceCount; i++) {
        if (dice[index][i] == bottom) {
            nBottomIndex = diceMatch[i];
            break;
        }
    }

    return nBottomIndex;
}

 

첫 번째 주사위의 아랫면은 고정시키기 때문에 두 번째부터 마지막 주사위까지 반복문을 돌며 주사위의 6면을 살펴보고 bottom과 같은 수가 나오면 해당 주사위의 윗면의 index를 알게 된다. diceMatch배열을 통해 해당 주사위의 아랫면 index를 찾은 후 return 한다.

 

아랫면 index를 통해 옆면의 최댓값 찾기

 

static int findMax(int index, int bottomIndex) {
    int max = 0;

    for (int i = 0; i < diceCount; i++) {
        if (i == bottomIndex || i == diceMatch[bottomIndex]) {
            continue;
        }
        if (max < dice[index][i]) {
            max = dice[index][i];
        }
    }

    return max;
}

 

해당 주사위의 아랫면과 윗면의 index를 제외한 값 중 반복문을 돌며 최댓값을 찾아내고 이를 return 한다.

 

최종 코드

 

public class BOJ_2116 {
    static int[][] dice;
    static final int diceCount = 6;
    static int[] diceMatch = {5, 3, 4, 1, 2, 0};  // A-F, B-D, C-E

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        dice = new int[N][diceCount];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < diceCount; j++) {
                dice[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = 0;

        for (int i = 0; i < diceCount; i++) {
            int bottom = dice[0][i];
            int totalMax = findMax(0, i);

            for (int j = 1; j < N; j++) {
                int nBottomIndex = findNextBottomIndex(j, bottom);
                totalMax += findMax(j, nBottomIndex);
                bottom = dice[j][nBottomIndex];
            }

            result = Math.max(totalMax, result);
        }

        System.out.println(result);
    }

    // index+1번째 주사위 아랫면 숫자로 다음 주사위 아랫면 index 찾기
    static int findNextBottomIndex(int index, int bottom) {
        int nBottomIndex = 0;

        for (int i = 0; i < diceCount; i++) {
            if (dice[index][i] == bottom) {
                nBottomIndex = diceMatch[i];
                break;
            }
        }

        return nBottomIndex;
    }

    static int findMax(int index, int bottomIndex) {
        int max = 0;

        for (int i = 0; i < diceCount; i++) {
            if (i == bottomIndex || i == diceMatch[bottomIndex]) {
                continue;
            }
            if (max < dice[index][i]) {
                max = dice[index][i];
            }
        }

        return max;
    }
}

 첫 번째 주사위의 아랫면을 1부터 6까지 고정시키며 옆 면의 최댓값을 구한 뒤 그중 가장 큰 값을 출력한다.