[백준] 2116 - 주사위 쌓기 (JAVA)

개츠비·2023년 6월 1일

백준

목록 보기

83/84

소요시간 : 1시간 15분
문제 사이트 : 백준
문제 수준 : 골드 5
문제 유형 : 구현, 브루트포스 알고리즘
다른 사람의 풀이를 참고 했는가 ? : X
문제 링크 : https://www.acmicpc.net/problem/2116
푼 날짜 : 2023.06.01

1. 사용한 자료구조 & 알고리즘

구현, 브루루트포스 알고리즘, 그리디 알고리즘

2. 사고과정

1. 옆면을 어떻게 구할 것인가?
👉 윗면, 아랫면이 아닌 숫자들은 4개가 나올 수 있다. 여기서 그리디 알고리즘을 사용해서, 4개의 면들 중 가장 큰 숫자들을 계속해서 더해주면 된다.

4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다.

의 조건이 있기 때문에, 옆면은 자유롭게 돌릴 수 있고, 옆면의 숫자들 중 가장 큰 숫자를 계속해서 더하면 된다.
2. 다음 주사위는 어떻게 올릴 것인가?
👉 이전의 주사위를 쌓고, 그 가장 윗면 숫자를 알 수 있다. 그렇다면 다음 주사위의 아랫면은 이전 주사위의 윗면 숫자일 것이다. 전개도를 따라서 보면
우리는 반대쪽 인덱스를 알 수 있다. (A-F), (B-D), (C-E) 로 연결되어 있으므로, 그를 이용해서 반댓면의 숫자를 구할 수 있다.

3. 그렇다면 처음에 맨 위에 숫자는 어떻게 정할 것인가?
👉 여기서 브루트포스 알고리즘을 사용한다. 가장 아래에 위치한 주사위의 가장 윗면이 1일때, 2일때 ... 6일 때 모두를 전부 구해야 한다.

3. 풀이과정

가장 아래의 주사위의 윗면이 1~6일때 모두 구함.
그 윗면에 따라서 주사위의 아랫면의 숫자도 함께 구함.
윗면의 숫자, 아랫면의 숫자가 아닌 숫자들 중 가장 높은 숫자를 sum에 저장.
그 다음 주사위는, 이전의 주사위들의 윗면의 숫자를 보고, 그 숫자와 똑같은 숫자의 주사위가 아랫면을, 그 반댓면 (A-F), (B-D), (C-E) 에 있는 숫자를 위에 놓는다. 반복할 때마다 윗면, 아랫면이 아닌 숫자들 중 가장 큰 숫자를 더해준다.

4. 소스코드

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


public class Main {

	static int dice[][];

	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][6];
		for(int i=0;i<n;i++) {
			st=new StringTokenizer(br.readLine());
			for(int j=0;j<6;j++) {
				dice[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int max= 0 ;
		for(int i=0;i<6;i++) {
			int sum = maxDice(i);
			max=Math.max(sum,max);
		}

		System.out.println(max);


	}
	public static int maxDice(int idx) {
		
		//newDice의 0번째 인덱스는 윗면, 1번째 인덱스는 아랫면으로 봄.
		int newDice[] = new int[2];
		//윗면을 구함.
		newDice[0] = dice[0][idx];
		//윗면에 따라서 아랫면을 구함.
		//주사위의 전개도를 보면 알 수 있음.
		switch(idx) {
		case 0: newDice[1] = dice[0][5]; break;
		case 1: newDice[1] = dice[0][3]; break;
		case 2: newDice[1] = dice[0][4]; break;
		case 3: newDice[1] = dice[0][1]; break;
		case 4: newDice[1] = dice[0][2]; break;
		case 5: newDice[1] = dice[0][0]; break;
		}
		int sum = 0;
		//sum은 윗면, 아랫면이 아닌 것들 중 가장 높은 숫자
		for(int i=0;i<6;i++) {
			if(dice[0][i]==newDice[0]||dice[0][i]==newDice[1]) continue;
			sum=Math.max(sum,dice[0][i]);
		}
		
		for(int i=1;i<dice.length;i++) {
			int max = 0;
			//이전 좌표의 윗면을 보고, 다음 위, 아랫면을 정함
			newDice = dice(i,newDice[0]);
			for(int j=0;j<dice[0].length;j++) {
				//윗면, 아랫면이 아닌 숫자 중 가장 큰 옆면을 구함
				if(dice[i][j]==newDice[0]||dice[i][j]==newDice[1]) continue;
				max=Math.max(max,dice[i][j]);
			}
			//가장 큰 옆면을 더해줌
			sum+=max;

			
		}
		


		//sum을 리턴
		return sum;
		
	}
	//몇번째 주사위인지, 이전의 주사위 위의 숫자가 무엇이었는지
	public static int [] dice (int idx,int prevTop) {
	
		//다음 주사위의 아랫면 숫자는 이전 주사위의 윗면 숫자
		int bottom = prevTop;

		//다음 주사위의 윗면을 구함
		int top = otherSideDice(idx,prevTop); 
	
		//위, 아래 숫자를 리턴
		return new int[] {top,bottom};
		
	}
	
	public static int otherSideDice(int idx,int prevTop) {
		int index= -1;
		int result = -1;
		//6개의 주사위 면을 보면서, 이전의 위 좌표를 찾으면 index는 i가 됨
		for(int i=0;i<6;i++) {
			if(dice[idx][i]==prevTop)
				index = i;
		}
		//주사위의 전개도를 보고, 그 반대면 숫자를 구할 수 있음.
		switch(index) {
		case 0 : result = dice[idx][5]; break;
		case 1 : result = dice[idx][3]; break;
		case 2 : result = dice[idx][4]; break;
		case 3 : result = dice[idx][1]; break;
		case 4 : result = dice[idx][2]; break;
		case 5 : result = dice[idx][0]; break;
		}
		//반대면 숫자를 리턴
		return result;
		
		
	}

}