[백준/Java] 1226번 : 주사위 쌓기

🌵 문제 분석

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

N개의 주사위를 아래 주사위의 윗면, 위 주사위의 밑면이 맞닿는 곳의 숫자가 일치하게 일렬로 쌓는다.

주사위를 쌓아서 만들어진 사각 기둥의 한 옆면의 합이 최대가 되도록 할 때, 한 옆면의 숫자의 합의 최댓값을 구하여라.

 

입력 :

N(주사위 개수)

N개의 주사위 전개도에 입력되는 숫자

🌵 구현 아이디어

1️⃣ 마주보는 면 저장

주사위의 숫자 위치가 고정되어있기 때문에 마주보는 면은 항상 정해져있다. 

opposite[i] = j -> i의 마주보는 면은 j임을 저장

2️⃣ 첫 번째 주사위의 윗면 결정

첫 번째 주사위의 윗면은 6개 중 하나가 될 수 있으므로 6가지 경우에 대해 최댓값을 찾는다.

3️⃣ 나머지 N-1개 주사위의 윗면 결정

첫 번째 주사위의 윗면이 정해지면 자동으로 두 번째 주사위의 밑면, 윗면이 결정된다.

그리고 연쇄적으로 세 번째, 네 번째, ..., N번째 주사위까지 밑면, 윗면이 결정된다.

4️⃣ 옆면의 최댓값 구하기

사각 기둥이 세워졌다면 각 주사위의 윗면, 밑면을 제외한 4개의 옆면 중 가장 큰 값을 사각 기둥의 한 면으로 오게 만든다.

그 값들을 모두 더하여 최댓값을 구한다.

 

2~4 과정을 첫 번째 주사위의 윗면을 6번 결정하는 동안 반복하며 사각 기둥 옆면의 최댓값을 갱신한 후 출력한다.

🌵 시간 복잡도

마주보는 면을 저장하는 시간 복잡도 : 주사위 갯수만큼 반복하므로 O(N)

첫 번째 주사위의 윗면을 결정하는 시간 복잡도 : 주사위 면의 갯수만큼 반복하므로 O(6)

나머지 N-1개의 주사위의 윗면을 결정하는 시간 복잡도 : N-1개의 주사위에 대해 수행하므로 O(N-1)

옆면의 최댓값을 구하는 시간 복잡도 : 4개의 면에 적힌 숫자를 정렬하는 과정을 N-1번 수행하므로 O(4log4)*O(N-1)

 

전체 시간 복잡도 : O(N)+(O(6)*(O(N-1)+O(4log4)*O(N-1)) = 1000 + (6*(1000+1000)) = 12000

따라서 2초 안에 연산 가능하다.

🌵 알고리즘

구현

🌵 코드 설계

1. 입력받기
   1. N에 주사위 개수 저장
   2. 이차원 배열 dice에 주사위 숫자 저장
2. opp 배열에 마주보는 면 저장
   1. A-F, B-D, C-E끼리 마주봄 -> 인덱스 0-5, 1-3, 2-4
   2. opp[0] = 5, opp[5] = 0
   3. opp[1] = 3, opp[3] = 1
   4. opp[2] = 4, opp[4] = 2
3. 첫 번째 주사위의 윗면 결정
   1. 윗면을 top으로 선언
   2. 0<=i<=5에 대하여
      1. top = dice[0][i] -> i, opp[i]가 위, 아래로 선정됨
      2. 인덱스가 i, opp[i]인 값 빼고 나머지 숫자 중 가장 큰 값을 maxVal에 더하기
   3. 2~N번째 주사위의 윗면 결정
      1. 1<=diceNum<=N-1에 대하여 0<=i<=5
         1. if(top == dice[diceNum][i]) top = dice[diceNum][opp[i]] -> i, opp[i]가 위, 아래로 선정됨
         2. // 아래쪽 주사위의 top에 적힌 숫자가 위쪽 주사위의 i 번째에 있다는 것을 찾았다면
         3. // 위쪽 주사위의 top을 i의 맞은편에 있는 숫자로 갱신함
         4. 인덱스가 i, opp[i]인 값 빼고 나머지 숫자 중 가장 큰 값을 maxVal에 더하기
   4. 최댓값 갱신 ans = Math.max(ans, maxVal);
4. ans를 출력

🌵 정답 코드

import java.io.*;
import java.util.*;

public class Main {
    static int N; // 주사위 개수
    static int[][] dice; // 주사위 정보를 저장하는 배열
    static int[] opp = {5, 3, 4, 1, 2, 0}; // 마주 보는 면의 인덱스

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dice = new int[N][6];

        // 주사위 입력 받기
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 6; j++) {
                dice[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int ans = 0; // 최댓값 저장

        // 첫 번째 주사위의 윗면 결정 (0~5번 인덱스를 윗면으로 선택)
        for (int i = 0; i < 6; i++) {
            int top = dice[0][i]; // 첫 번째 주사위의 윗면 값
            int bottom = dice[0][opp[i]]; // 첫 번째 주사위의 아랫면 값
            int maxVal = getMaxSide(0, i, opp[i]); // 첫 번째 주사위의 최댓값

            // 2~N번째 주사위의 윗면 결정
            for (int diceNum = 1; diceNum < N; diceNum++) {
                for (int j = 0; j < 6; j++) {
                    if (top == dice[diceNum][j]) { // 이전 층의 윗면(top)이 현재 주사위의 어느 면인지 찾음
                        bottom = dice[diceNum][j]; // 현재 주사위의 아랫면
                        top = dice[diceNum][opp[j]]; // 현재 주사위의 윗면
                        maxVal += getMaxSide(diceNum, j, opp[j]); // 현재 주사위의 최댓값을 더함
                        break; // 찾았으면 반복 종료
                    }
                }
            }

            ans = Math.max(ans, maxVal); // 최댓값 갱신
        }

        System.out.println(ans); // 최댓값 출력
    }

    // 현재 주사위에서 윗면, 아랫면을 제외한 숫자 중 최댓값 반환
    static int getMaxSide(int diceNum, int bottomIdx, int topIdx) {
        int maxSide = 0;
        for (int j = 0; j < 6; j++) {
            if (j != bottomIdx && j != topIdx) { // 윗면, 아랫면 제외
                maxSide = Math.max(maxSide, dice[diceNum][j]);
            }
        }
        return maxSide;
    }
}