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

문제

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

 

풀이 방법

구현문제로 브루투포스 알고리즘을 사용하면 된다.
우선 나는 문제에 있는 ABCDEF을 보고 각 마주보는 면의 인덱스를 미리 저장해뒀다.
다음과 같은 순서로 구현했다.
1. 맨 아래에 올 주사위의 윗면을 정해준다. (6면 전부 다 구해보기)
2. 윗면이 정해졌으면 옆면중에서 가장 큰값을 고른다.
3. 윗면의 값과 위에서 골랐던 옆면 중 가장 큰값을 가지고 주사위를 쌓으러 간다.
//재귀함수 시작 (아래서 2번째 주사위부터 쌓아올리는 함수)
1. 아래에 있는 주사위의 윗면에 해당하는 값을 현재 주사위에서 찾는다.
=> 자동으로 윗면의 인덱스가 정해진다.
2.  옆면중에서 가장 큰값을 고른다.
3. 그 다음 주사위를 쌓으러 간다.
// 주사위를 다 쌓을때 까지  1~3번을 반복한다. 
4. 주사위를 다 쌓으면 현재 max에 저장된 값과 현재 sum값을 비교해서 더 큰 값을 넣는다. 

 

제출 코드

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

public class BJ_2116_주사위쌓기 {
	static int N, Max;
	static int[][] dice;
	static int[] op = { 5, 3, 4, 1, 2, 0 }; //각 마주보는 면의 인덱스를 저장

	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()); // 주사위 개수

		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());
			 }
		}
		Max = -1;
		//윗 면 정하기 
		for (int i = 0; i < 6; i++) {
			int max = 0;
			for (int j = 0; j <6; j++) { //옆면 중에서 가장 큰 값 
				if( j ==i || j == op[i]) continue;
				max = Math.max(max,  dice[0][j]);
			}
			up(dice[0][i] , max, 1); //윗면의 "값"과 옆면중에서 가장 큰 값
		}
		System.out.println(Max);
	}

	private static void up(int top, int sum, int cnt) { //cnt: 현재까지 올린 주사위 개수
		if(cnt == N) {
			Max = Math.max(sum, Max);
			return ;
		}
		//현재 주사위에서 top에  해당하는 인덱스를 찾아야함
		int idx=0;
		for (int i = 0; i <6; i++) { //이전 주사위의 탑에 해당하는 값을 현재 주사위에서 찾기
			if(dice[cnt][i] == top) {
				idx =i; 
				break;
			}
		}
		int nextTop = op[idx]; //현재 주사위의 윗면의 인덱스 결정
		int m = 0;
		for (int j = 0; j <6; j++) { //옆면중에서 가장 큰 값 
			if( j ==nextTop || j == idx) continue;
			m = Math.max(m,  dice[cnt][j]);
		}
		up(dice[cnt][nextTop], sum+m, cnt+1);
	}
}