[BOJ 2116] 주사위 쌓기

문제

주사위 쌓기

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

 

 

풀이

설명

주사위들을 규칙에 따라 쌓아 올렸을 때, 한 옆면의 숫자의 합이 가장 큰 값을 구하는 문제입니다.

 

주사위에 대한 설명입니다.

주사위는 모두 크기가 같은 정육면체이며, 각 면에는 1부터 6까지의 숫자가 적혀있습니다. 그러나 마주 보는 면에 적힌 숫자의 합이 반드시 7인 것은 아닙니다.

 

주사위를 쌓는 규칙은 다음과 같습니다.

• 아래에서부터 1번, 2번, 3번, ..., N번 주사위 순으로 쌓습니다.
• 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀있는 숫자는 위에 있는 주사위의 아랫면에 적혀있는 숫자와 같아야 합니다.
  e.g. 1번 주사위의 윗면에 있는 숫자 = 2번 주사위의 아랫면에 있는 숫자
• 각 주사위는 위 아래를 고정한 채 옆으로 90도, 180도, 또는 270도 회전시킬 수 있습니다.

 

주사위 눈 입력에 대한 설명입니다.

각 주사위 눈은 A, B, C, D, E, F 순으로 입력되며, A와 F, B와 D, C와 E가 마주 봅니다.

 

DP를 이용해 해결할 수 있습니다.

dp[i][j]는 i번째 주사위의 밑면이 j일 때, 옆면의 숫자 합의 최댓값입니다.

 

주사위 눈을 계산하기 위해 dice 배열을 사용했습니다.

dice[i][j]는 i번째 주사위에서 값이 j인 면의 반대편 값입니다.

e.g. j = A인 경우, dice[i][j] = F

 

dp[i][j]는 dice[i - 1]까지 계산했을 때 옆면의 합의 최댓값 + dice[i]의 옆면 중 최댓값입니다.

이때, dice[i -1]의 윗면과 dice[i]의 아랫면이 같아야 함을 유의해야 합니다.

dice[i]의 옆면의 값에는 j와 dice[i][j]가 포함될 수 없습니다.

 

dp[i][j]의 점화식은 다음과 같습니다.

dp[i][j] = dp[i - 1][dice[i - 1][j] + dice[i]의 옆면 중 최댓값

 

예시 코드

function solution() {
  const MAX_DIE_VALUE = 6;

  const N = Number(input());
  // dice[i][j] = i번째 주사위에서 값이 j인 면의 반대편 값
  const dice = Array.from({ length: N + 1 }, () =>
    Array(MAX_DIE_VALUE + 1).fill(0)
  );
  const dieValues = [1, 2, 3, 4, 5, 6];
  // dp[i][j] = i번째 주사위의 밑면이 j일 때, 옆면의 숫자 합의 최댓값
  const dp = Array.from({ length: N + 1 }, () =>
    Array(MAX_DIE_VALUE + 1).fill(0)
  );

  for (let i = 1; i <= N; i++) {
    const [A, B, C, D, E, F] = input().split(" ").map(Number);
    const die = dice[i];
    die[A] = F;
    die[B] = D;
    die[C] = E;
    die[D] = B;
    die[E] = C;
    die[F] = A;
  }

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= MAX_DIE_VALUE; j++) {
      const acc = dp[i - 1][dice[i - 1][j]];
      const currMaxSideVal = Math.max(
        ...dieValues.filter((v) => v !== j && v !== dice[i][j])
      );
      dp[i][j] = acc + currMaxSideVal;
    }
  }

  return Math.max(...dp[N]);
}