12869 뮤탈리스크

문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

=====

문제 분석

각 scv에 대해 체력을 기준으로 완전 탐색을 통해 문제를 해결하였다.

처음에는 scv를 체력순으로 내림차순하여 각 자리에 9,3,1을 빼줬는데 첫번 쨰 입출력 같이

꼭 가장 큰 값에 9를 빼는 것이 해결책이 되는 것은 아니었다.

따라서 가능한 모든 경우의 수를 탐색해야 했는데 이럴 경우, 중복 되는 경우가 생길 수가 있었기 때문에 visited를 선언하여 경우의 수를 최소화해주었다.

visited = Array.from({ length: arr[0] + 1 }, () =>
    Array.from({ length: arr[1] + 1 }, () =>
        Array.from({ length: arr[2] + 1 }, () => -1)
    )
);

뮤탈리스크의 공격으로 각 자리의 수들이 체력이 빠지는 경우는 아래와 같다.

visited[arr[0]][arr[1]][arr[2]] = 0;
const dx = [
    [9, 3, 1],
    [9, 1, 3],
    [3, 9, 1],
    [3, 1, 9],
    [1, 3, 9],
    [1, 9, 3],
];

이때 scv수가 3개가 아닐 경우 계산이 귀찮아질 수 있어서 길이가 3보다 작을 시 0을 추가해줌

while (arr.length < 3) {
    arr.push(0);
}

이후에는 BFS 방식으로 탐색하였다.

const q = [[...arr, 0]];
    while (q.length) {
        const [x, y, z, cnt] = q.shift();
        if (x <= 0 && y <= 0 && z <= 0) {
            console.log(cnt);
            process.exit(0);
        }
        for (let i = 0; i < 6; i++) {
            const nx = aa(x - dx[i][0]);
            const ny = aa(y - dx[i][1]);
            const nz = aa(z - dx[i][2]);
        if (visited[nx][ny][nz] !== -1) continue;
	    visited[nx][ny][nz] = visited[x][y][z] + 1;
        q.push([nx, ny, nz, cnt + 1]);
    }
}

 

정답 코드

const aa = (value) => {
    if (value <= 0) return 0;
    return value;
};
const main = (n, arr) => {
    while (arr.length < 3) {
        arr.push(0);
    }
    arr.sort((a, b) => b - a);
    visited = Array.from({ length: arr[0] + 1 }, () =>
        Array.from({ length: arr[1] + 1 }, () =>
            Array.from({ length: arr[2] + 1 }, () => -1)
        )
    );
    visited[arr[0]][arr[1]][arr[2]] = 0;
    const dx = [
        [9, 3, 1],
        [9, 1, 3],
        [3, 9, 1],
        [3, 1, 9],
        [1, 3, 9],
        [1, 9, 3],
    ];

    const q = [[...arr, 0]];
    while (q.length) {
        const [x, y, z, cnt] = q.shift();
        if (x <= 0 && y <= 0 && z <= 0) {
            console.log(cnt);
            process.exit(0);
        }
        for (let i = 0; i < 6; i++) {
            const nx = aa(x - dx[i][0]);
            const ny = aa(y - dx[i][1]);
            const nz = aa(z - dx[i][2]);
            if (visited[nx][ny][nz] !== -1) continue;
            visited[nx][ny][nz] = visited[x][y][z] + 1;
            q.push([nx, ny, nz, cnt + 1]);
        }
    }
};

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map((v) => +v);
main(n, arr);