[BOJ] 2116 주사위쌓기 - JAVA

1. 문제

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

2116번: 주사위 쌓기

천수는 여러 종류의 주사위를 가지고 쌓기 놀이를 하고 있다. 주사위의 모양은 모두 크기가 같은 정육면체이며 각 면에는 1부터 6까지의 숫자가 하나씩 적혀있다. 그러나 보통 주사위처럼 마주 보는 면에 적힌 숫자의 합이 반드시 7이 되는 것은 아니다.

주사위 쌓기 놀이는 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위, … 의 순서로 쌓는 것이다. 쌓을 때 다음과 같은 규칙을 지켜야 한다: 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 한다. 다시 말해서, 1번 주사위 윗면의 숫자는 2번 주사위 아랫면의 숫자와 같고, 2번 주사위 윗면의 숫자는 3번 주사위 아랫면의 숫자와 같아야 한다. 단, 1번 주사위는 마음대로 놓을 수 있다.

이렇게 쌓아 놓으면 긴 사각기둥이 된다. 이 사각기둥에는 4개의 긴 옆면이 있다. 이 4개의 옆면 중에서 어느 한 면의 숫자의 합이 최대가 되도록 주사위를 쌓고자 한다. 이렇게 하기 위하여 각 주사위를 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 돌릴 수 있다. 한 옆면의 숫자의 합의 최댓값을 구하는 프로그램을 작성하시오.

---

2. 풀이

메인

• 첫번째 주사위는 모든 경우를 다 돌려볼 수 있으므로 1부터 6까지 반복하면서 아랫면을 설정한다.
• stackDice의 반환 값 중 가장 큰 값을 저장한다.

static int[][] dice;
static int N;
static int[] pair = {5, 3, 4, 1, 2, 0};

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;

   N = Integer.parseInt(in.readLine());
   dice = new int[N][6];
   for (int i = 0; i < N; i++) {
      st = new StringTokenizer(in.readLine());
      for (int j = 0; j < 6; j++) {
         dice[i][j] = Integer.parseInt(st.nextToken());
      }
   }

   int max = Integer.MIN_VALUE;
   for (int i = 1; i <= 6; i++) {
      max = Math.max(max, stackDice(0, i, 0));
   }

   System.out.println(max);
}

 

주사위 쌓는 메서드

• 파라미터는 이전까지 쌓은 주사위의 개수(cnt), 아랫면으로 만들어야 할 값(bottom), 지금까지의 합계(sum)이다.
• 주사위를 N개 쌓았다면 그 동안의 합계를 반환하고 끝낸다. 
• 인덱스 값으로 0부터 5까지 반복한다.
  • 파라미터로 받은 아랫면의 값이 [cnt번의 주사위 i에 저장된 값]과 일치하면 반복문의 처음으로 돌아간다.
  • 아랫면의 값이 [cnt번의 주사위 중 i의 페어에 저장된 값]과 일치하면 다음 주사위에 넘길 아랫면 값을 저장하고 반복문의 처음으로 돌아간다.
  • 이 두 경우가 아니라면 옆면이라는 의미다. 옆 면 중 가장 큰 값을 max에 저장한다.
• 탐색이 끝나면 다음 주사위를 불러서 그 반환 값을 같이 리턴한다. 

private static int stackDice(int cnt, int bottom, int sum) {
   if (cnt == N) return sum;

   int max = 0;
   int nBottom = 0;
   for (int i = 0; i < 6; i++) {
      if (bottom == dice[cnt][i]) continue;
      if (bottom == dice[cnt][pair[i]]) {
         nBottom = dice[cnt][i];
         continue;
      }
      max = Math.max(max, dice[cnt][i]);
   }

   return stackDice(cnt + 1, nBottom, sum + max);
}

---

3. 결과

pair 배열을 처음에 stackDice함수 안에 넣었다가 static으로 하면 어떨지 궁금해서 바꿔 제출해보았다. 그리고 어차피 주사위는 1~6이니 처음 주사위의 아랫면을 고를 때 인덱스로 접근(dice[0][i])하지 않고 바로 i를 넣었다. 

중간의 틀렸습니다<-는 i로 바꾸는 와중에 0부터 시작해버려서 틀린 것이다. 

static으로 바꾸고, 인덱스 접근을 빼니 메모리면에서 좀 더 효율성이 좋아졌다. 시간은 아주 미세하게 더 들었지만 이 정도는 비슷하다고 봐도 될 것 같다.