[백준, Java] 2116번 주사위 쌓기
문제풀이
브루트포스 알고리즘으로 완전 탐색해야하는 문제이다.
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
arr = new int[N][6];
int max = Integer.MIN_VALUE;
for(int i=0; i<N; i++) {
st = new StringTokenizer(bf.readLine());
for(int j=0; j<6; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}1. 문제에서 주어진 입력을 받는다. 배열의 크기는 행 : N , 열 : 6 (주사위는 6면) 이다.
변수 max는 최대값을 담기 위한 변수이다.
for(int i=0; i<6; i++) {
int sum = 0;
int top = i;
int bottom = checkTop(i);2. 반복은 전체적으로 6번을 해야한다.
이유는 주사위의 눈은 총 6개(1,2,3,4,5,6)이므로 각각 주사위의 윗면에 올라왔을 때에 따라 나눠서 비교해야하기 때문이다.(사진 참고)
sum은 최대값을 더할 변수이고, 주사위의 윗면과 아랫면에 대한 인덱스 값을 담을 변수를 생성한다.
sum += checkBeside(0, top, bottom);3. checkBeside 함수로 옆면의 값들 중 가장 큰 값을 구한다.
매개변수는 총 3개이다.
첫 번째 매개변수는 몇 번째 주사위에 해당하는지(현재 0이 의미하는것은 1번 주사위를 의미),
두 번째 매개변수인 top은 현재 주사위의 윗면 인덱스 값,
세 번째 매개변수인 bottom은 현재 주사위의 아랫면 인덱스 값이다.
private static int checkBeside(int idx, int a, int b) {
int maxValue = 0;
for(int i=0; i<6; i++) {
if(i != a && i != b) {
maxValue = Math.max(maxValue, arr[idx][i]);
}
}
return maxValue;
}4. checkBeside 함수에서는 현재 주사위의 옆면 값(총 4개) 중 가장 큰 값을 return 한다.
매개변수 a,b는 각각 주사위의 윗면 인덱스 값, 아랫면 인덱스 값이기 때문에 이에 해당하지 않는 값들만 비교한다.
for(int j=1; j<N; j++) {
// top과 같은 숫자를 갖는게 몇 번째 인덱스에 있는지 찾기.
for(int k=0; k<6; k++) {
if(arr[j][k] == arr[j-1][top]) {
bottom = k;
top = checkTop(bottom);
sum += checkBeside(j, top, bottom);
break;
}
}
}5. 다음 반복은 1부터 N번까지 반복한다.
1~N이 의미하는 것은 총 N개의 주사위가 있으면 1번 주사위를 제외한 나머지 주사위에 대해 반복하는 것이다.
(1번 주사위는 3,4번에서 실행했음.)
1번 주사위의 윗면의 값에 따라서 나머지 N-1개의 주사위들은 자동으로 값이 결정된다.
반복문이 한 번 더 실행되는데 이 때의 반복문은 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자가 같아야하기 때문에 1번 주사위 윗면의 숫자가 2번 주사위의 몇 번째 인덱스에 있는지 찾기 위함이다.
조건을 만족해 찾았다면 bottom과 top의 값을 갱신한다.
그리고 윗면과 아랫면의 인덱스를 찾았으니 checkBeside 함수로 최대값을 갖는 옆 면의 값을 찾는다.
max = Math.max(max, sum);6. 5번을 반복하면 sum에는 N개의 주사위 옆면에 대한 합의 최댓값이 들어있을 것이다.
우리는 이를 총 6번 반복해야하기 때문에 한 주사위 사이클에 대한 반복이 끝날 때마다 최댓값을 갱신해준다.
System.out.println(max);7. 결과를 출력한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[][] arr;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
int N = Integer.parseInt(st.nextToken());
arr = new int[N][6];
int max = Integer.MIN_VALUE;
for(int i=0; i<N; i++) {
st = new StringTokenizer(bf.readLine());
for(int j=0; j<6; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// 첫번째 주사위에 대해 6번 반복
for(int i=0; i<6; i++) {
int sum = 0;
int top = i;
int bottom = checkTop(i);
sum += checkBeside(0, top, bottom);
// 총 N개의 주사위 중 N-1개의 주사위를 반복해야함.
for(int j=1; j<N; j++) {
// top과 같은 숫자를 갖는게 몇 번째 인덱스에 있는지 찾기.
for(int k=0; k<6; k++) {
if(arr[j][k] == arr[j-1][top]) {
bottom = k;
top = checkTop(bottom);
sum += checkBeside(j, top, bottom);
break;
}
}
}
// 최댓값 비교
max = Math.max(max, sum);
}
System.out.println(max);
}
private static int checkTop(int i) {
int bottom = 0;
if(i == 0) bottom = 5;
else if( i == 1) bottom = 3;
else if( i == 2) bottom = 4;
else if( i == 3) bottom = 1;
else if( i == 4) bottom = 2;
else if( i == 5) bottom = 0;
return bottom;
}
private static int checkBeside(int idx, int a, int b) {
int maxValue = 0;
for(int i=0; i<6; i++) {
if(i != a && i != b) {
maxValue = Math.max(maxValue, arr[idx][i]);
}
}
return maxValue;
}
}
https://www.acmicpc.net/problem/2116