수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.
각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.
뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.
- 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
- 두 번째로 공격받는 SCV는 체력 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 |