99클럽 코테 스터디 25일차 TIL

백준 - 2116번

 

각 주사위의 윗면은 이전 주사위의 아랫면과 일치해야 한다는 규칙에 맞게,

주사위마다 아랫면과 윗면을 정하고 옆면의 최댓값을 구해야 한다.

그리고 ABCDEF 중 정해진 아랫면과 윗면이 없어 모든 경우를 고려해야 한다.

 

주사위의 마주 보는 면을 구할 때 (0,5) , (1,3) , (2,4) 관계가 고정이므로 해당 조건에 맞게 윗면, 아랫면을 구해야 한다.

구해진 면의 주사위 값을 제외한 최댓값을 찾고, 주사위마다 이 과정을 반복한다.

 

구현

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] dices = new int[N][6]; // 주사위 데이터를 저장

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

        // 반대 면을 구하기 위한 배열
        int[] opposite = {5, 3, 4, 1, 2, 0};

        int maxSum = 0;

        // 첫 번째 주사위의 아랫면 선택
        for (int i = 0; i < 6; i++) {
            int sum = 0;
            int bottom = dices[0][i]; // 첫 주사위의 아랫면
            int top = dices[0][opposite[i]]; // 첫 주사위의 윗면

            // 첫 번째 주사위의 옆면 최댓값
            sum += getMaxSide(bottom, top);

            // 이후 주사위 처리
            for (int j = 1; j < N; j++) {
                int bottomIdx = findIndex(dices[j], top); // 이전 윗면이 현재 주사위의 아랫면
                bottom = dices[j][bottomIdx];
                top = dices[j][opposite[bottomIdx]];
                sum += getMaxSide(bottom, top);
            }

            maxSum = Math.max(maxSum, sum);
        }

        System.out.println(maxSum);
    }

    // 아랫면과 윗면을 제외한 옆면 중 최댓값 구하기
    private static int getMaxSide(int bottom, int top) {
        int max = 0;
        for (int i = 1; i <= 6; i++) {
            if (i != bottom && i != top) {
                max = Math.max(max, i);
            }
        }
        return max;
    }

    // 배열에서 값을 찾고 인덱스 반환
    private static int findIndex(int[] dice, int value) {
        for (int i = 0; i < dice.length; i++) {
            if (dice[i] == value) {
                return i;
            }
        }
        return -1; // 없는 경우는 발생하지 않음
    }
}

---

브루트 포스

brute : 무식한, force : 힘

브루트 포스(Brute Force) 알고리즘은 가능한 모든 경우의 수를 탐색하여 해결하는 방식이다.

모든 경우의 수를 전부 탐색하기 때문에 100%의 정확성을 보장하지만 반대로 높은 시간 복잡도를 가진다.

 

완전 탐색과 브루트 포스

의미 차이가 거의 없어 같은 의미로 쓰이기도 한다.

• 완전 탐색 : 모든 경우의 수를 전부 탐색
• 브루트포스 : 문제 해결을 위해, 모든 경우를 탐색하고 답을 도출

작은 차이라면 완전 탐색은 탐색의 과정에 중점을 두고, 브루트포스는 결과를 찾는 것에 중점을 둔다.

---

백준 2116번 - 주사위 쌓기

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