BOJ 2116 주사위 쌓기 (Java)

문제 탐색하기

• 보통 주사위처럼 마주 보는 면에 적혀진 숫자의 합이 반드시 7이 되지 않는다.
• 1번 주사위는 마음대로 놓을 수 있다.
• N-1번째 주사위의 윗면의 숫자 = N번째 주사위의 아랫면의 숫자가 되어야 한다.

이때, 한 옆면의 숫자 합의 최대값을 구한다.

코드 설계하기

최대값을 가지려면 옆면으로 최대한 주사위 값이 6, 5, 4가 오도록 해야 한다.

• 6이 되는 경우 : 윗면, 아랫면에 6이 없음
• 5가 되는 경우 : 윗면 혹은 아랫면에 6이 있고 그 반댓면은 5가 아니다.
• 4가 되는 경우 : 윗면과 아랫면이 각각 6, 5가 된다.

구현 방법

1. 입력 처리 (O(N))
   • N 개의 주사위를 입력받아 2D 배열 dices 에 저장한다.
   • 각 주사위는 6개의 숫자를 가지며, dices[i][j] 는 i번째 주사위의 j번째 면 숫자이다.
2. 가능한 바닥면(밑면) 탐색 (O(6 * N))
   • 밑면(아랫면) 숫자는 1~6 중 하나가 될 수 있다.
   • calcMax(floor) 함수를 이용해 밑면이 floor일 때, 최대 가능한 측면 숫자의 합을 구한다.
   • 모든 경우 중 최댓값을 answer에 저장한다.
3. calcMax(floor) 실행 과정 (O(N))
   • 첫 번째 주사위의 밑면을 floor로 설정하고, 윗면(ceil)을 findOppositeSide를 이용해 찾음.
   • 이후 N개의 주사위를 순차적으로 확인하며, 주어진 조건에 따라 가능한 측면 최대값을 누적한다.
4. findOppositeSide(i)로 주어진 면의 반대쪽 면 찾기 (O(1))
   • 주사위에서 특정 면의 반대편 인덱스를 반환하는 역할

시간 복잡도

• 입력 처리: O(N)
• 가능한 바닥면 6가지 탐색: O(6 * calcMax)
• calcMax(floor): O(N) (각 주사위를 한 번씩만 탐색)
• 최종 시간 복잡도: O(6N) → O(N)
  • N이 10,000이어도 6배 정도이므로 시간 내에 연산이 충분히 가능하다.

정답 코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static int N, answer;
    private static int[][] dices;

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

        // 값 입력 및 초기화
        N = Integer.parseInt(st.nextToken());
        answer = 0;
        dices = new int[N][6];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 6; j++) {
                dices[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 바닥 면으로 가능한 값 1 ~ 6까지 전부 순회해서 가능한 최댓값 찾음
        for (int i = 1; i <= 6; i++){
            answer = Math.max(answer, calcMax(i));
        }

        System.out.println(answer);
    }

    private static int calcMax(int floor) {
        // 밑면의 값에 따라 최대가 되는 값 계산
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 6; j++) {
                if (dices[i][j] == floor) {
                    int ceil = dices[i][findOppsiteSide(j)];

                    if (floor == 6 || ceil == 6) {
                        if (floor == 5 || ceil == 5) {
                            // 밑면, 윗면 둘다 6 또는 5
                            res += 4;
                        } else {
                            // 밑면, 윗면이 6이고 5 미포함
                            res += 5;
                        }

                    } else {
                        // 밑면 윗면 둘다 6 아님 (옆면으로 6 OK)
                        res += 6;
                    }

                    // 현재 밑면을 윗면으로 설정
                    floor = ceil;
                    break;
                }
            }
        }
        return res;
    }

    private static int findOppsiteSide(int i){
        switch(i){
            case 0:
                return 5;
            case 1:
                return 3;
            case 2:
                return 4;
            case 3:
                return 1;
            case 4:
                return 2;
            case 5:
                return 0;
            default:
                return -1;
        }
    }
}