본문 바로가기
코딩 테스트/백준

12869 뮤탈리스크

by 위그든씨 2025. 1. 3.

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 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);

'코딩 테스트 > 백준' 카테고리의 다른 글

13398 연속합2  (0) 2025.01.04
5557번 1학년 (자바스크립트)  (0) 2025.01.04
2133 타일 채우기  (0) 2025.01.03
2225 합분해 (자바스크립트)  (0) 2025.01.03
30242 N-Qeen(Easy)  (0) 2025.01.02