[백준] 1041 주사위 (Javascript)

문제

BOJ1041_주사위

풀이

이 문제는 직접 그림으로 그려보면 방법을 떠올리기가 쉽다.
$N^3$개의 주사위로 정육면체를 만들었다고 가정해보자.

이 정육면체를 구성한 주사위의 한 면만 보이는 부분은 아래와 같을 것이다.

그리고 주사위의 인접한 두 면만 보이는 부분은 아래와 같다.

마지막으로 주사위의 인접한 세 면이 보이는 부분은 아래와 같다.

이렇게 구성하면 정육 면체의 모든 부분이 채워진다.

해당 정육면체에서 빨간 영역은 주사위의 한 면만 보이는 부분이기 때문에 주사위의 가장 작은 눈금이 왔을 때 최솟값을 갖는다.

초록색 영역은 주사위의 인접한 두 면의 합이 최소인 조합을 선택하면 된다. 인접한 두 면이란 마주보지 않는 두 면을 말한다.

파란색 영역은 주사위의 인접한 세 면의 합이 최소인 조합을 선택하면 된다. 인접한 세 면이란 각각의 면이 서로 마주보지 않는 세 개의 면을 말한다.

예를 들어 주사위의 눈금이 1 2 3 4 5 6 일 경우,

우선 주사위의 두 면의 합과, 세 면의 합을 구할 때 각각의 면들이 서로 마주보고 있는지 아닌지 확인해 주기 위해 마주보는 면의 인덱스를 저장하는 배열을 만들어야 한다.

const across = [5, 4, 3, 2, 1, 0];

그리고 최솟값을 구해주자

한 면만 보이는 부분 = 1

let min1 = Math.min(...dice);

두 면이 보이는 부분 = 1+2

let min2 = Infinity;

for (let i = 0; i < 6; i++) {
    for (let j = i + 1; j < 6; j++) {
        if (j === across[i]) continue; // 두 면이 맞은 편이라면 스킵
        min2 = Math.min(min2, dice[i] + dice[j]);
    }
}

세 면이 보이는 부분 = 1+2+3

let min3 = Infinity;
for (let i = 0; i < 6; i++) {
    for (let j = i + 1; j < 6; j++) {
        if (j === across[i]) continue;
        for (let k = j + 1; k < 6; k++) {
            if (k === across[i] || k === across[j]) continue; // 세 면 중 하나라도 맞은 편이라면 스킵
            min3 = Math.min(min3, dice[i] + dice[j] + dice[k]);
        }
    }
}

그리고 이렇게 구한 값을 주사위의 개수에 맞게 더해준다.

let sum1 = ((N - 2) * (N - 1) * 4 + (N - 2) ** 2) * min1;
let sum2 = ((N - 1) * 4 + (N - 2) * 4) * min2;
let sum3 = min3 * 4;

또한 N=1일 경우(주사위가 한 개인 경우)에는 위의 공식이 성립하지 않기 때문에, 모든 눈금을 합하고 그 중 최댓값을 빼서, 최소합을 만들어주면 된다.

N === 1 ? dice.reduce((acc, cur) => (acc += cur), 0) - Math.max(...dice)

완성된 코드는 아래와 같다.

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const dice = input[1].split(' ').map(Number);
const across = [5, 4, 3, 2, 1, 0];

let min1 = Math.min(...dice);
let min2 = Infinity;
let min3 = Infinity;

for (let i = 0; i < 6; i++) {
    for (let j = i + 1; j < 6; j++) {
        if (j === across[i]) continue; // 두 면이 맞은 편이라면 스킵
        min2 = Math.min(min2, dice[i] + dice[j]);
    }
}

for (let i = 0; i < 6; i++) {
    for (let j = i + 1; j < 6; j++) {
        if (j === across[i]) continue;
        for (let k = j + 1; k < 6; k++) {
            if (k === across[i] || k === across[j]) continue; // 세 면 중 하나라도 맞은 편이라면 스킵
            min3 = Math.min(min3, dice[i] + dice[j] + dice[k]);
        }
    }
}

let sum1 = ((N - 2) * (N - 1) * 4 + (N - 2) ** 2) * min1;
let sum2 = ((N - 1) * 4 + (N - 2) * 4) * min2;
let sum3 = min3 * 4;

// 주사위가 하나인 케이스 고려
console.log(N === 1 ? dice.reduce((acc, cur) => (acc += cur), 0) - Math.max(...dice) : sum1 + sum2 + sum3);