뮤탈리스크

문제

언어

  • JavaScript

순서도

  1. 점화식을 정의하고, 그에 맞게 dp 배열 생성하기
  2. dp 배열의 base 값 정의
  3. 점화식과 base 값을 이용해서 dp 배열 채우기
  4. dp[N - 1] 에서 최댓값 찾아서 출력

문제 풀이 step 1

  • 수빈이는 강호와 함께 스타크래프트 게임을 하고 있습니다.
  • 수빈이는 뮤탈리스크 1 개가 남아있고, 강호는 SCV N 개가 남아 있습니다.
  • 각각의 SCV 는 남아잇는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없습니다. 즉, 이 게임은 수빈이가 이겼다는 것입니다.
  • 뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV 를 공격할 수 있습니다.
    1. 첫 번째로 공격받는 SCV 는 체력 9 를 잃습니다.
    2. 두 번째로 공격받는 SCV 는 체력 3 을 잃습니다.
    3. 세 번째로 공격받는 SCV 는 체력 1 을 잃습니다.
  • SCV 의 체력이 0 또는 그 이하가 되어버리면, SCV 는 그 즉시 파괴됩니다. 한 번의 공격에서 같은 SCV 를 여러번 공격할 수는 없습니다.
  • 남아있는 SCV 의 체력이 주어졌을 때, 모든 SCV 를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 문제입니다.

문제 풀이 step 2

  • dp[x][y][z] = 각 SCV 의 체력이 x, y, z 인 경우 모든 SCV 를 파괴하기 위해 공격해야 하는 횟수의 최솟값
    • dp[9][3][1] = 1 이라면, 각 SCV 의 체력이 9, 3, 1 인 경우 모든 SCV 를 파괴하기 위해 공격해야 하는 쵯수는 1 이라는 뜻
  • DP 의 특징인 “작은 문제의 해답으로부터 큰 문제의 해답을 찾는다” 를 이용합니다.
  • 점화식은 다음과 같습니다.
    • dp[x][y][z] = Math.min(dp[x - 9][y - 3][z - 1], dp[x - 9][y - 1][z - 3], dp[x - 3][y - 9][z - 1], dp[x - 1][y - 9][z - 3], dp[x - 3][y - 1][z - 9], dp[x - 1][y - 3][z - 9]) + 1
  • 점화식을 위와 같이 정의한 이유는 다음과 같습니다.
    • 모든 SCV 를 공격할 수 있는 방법은 총 6 가지입니다.
      1. 9, 3, 1 순으로 때리기
      2. 9, 1, 3 순으로 때리기
      3. 3, 9, 1 순으로 때리기
      4. 1, 9, 3 순으로 때리기
      5. 3, 1, 9 순으로 때리기
      6. 1, 3, 9 순으로 때리기
    • 따라서 현재 남아있는 SCV 의 체력을 기준으로 6 가지 방법을 적용해서 그 중에 최솟값으로 정하면 됩니다.
  • base 값은 각 SCV 의 체력이 0 인 경우로, 값은 0 이 되겠습니다.
  • base 값과 점화식을 이용해서 dp 배열을 다 채운 후에 원하는 값을 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 본 문제는 점화식을 만들어내는 것이 좀 어려웠던 것 같습니다.
  • 처음에는 dp 배열을 dp[0][1] ~ dp[0][6] 으로 만들려고 했는데, 이러면 점화식도 안나오고, dp 배열의 의미도 이상했습니다.
  • 그래서 시행착오를 겪으면서, dp 배열을 횟수로 만들 수 있을까 라는 생각이 계기가 되어서, 점화식을 구할 수 있었던 것 같습니다.
  • 역시 DP 의 핵심은 이전에 만들어놓은 해답을 이용해서 현재의 해답을 찾는다 인 것 같습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// 총 6 가지 방법
const dir = [
	[9, 3, 1],
	[9, 1, 3],
	[3, 9, 1],
	[1, 9, 3],
	[3, 1, 9],
	[1, 3, 9],
];

const solution = (input) => {
	const n = Number(input[0]);
	let [x, y, z] = input[1].split(" ").map(Number);
	if (y === undefined) y = 0;
	if (z === undefined) z = 0;

	const dp = Array.from(Array(61), () =>
		Array.from(Array(61), () => Array(61).fill(0))
	);

	// base
	dp[0][0][0] = 0;

	// bottom-up
	for (let i = 0; i < 61; i++) {
		for (let j = 0; j < 61; j++) {
			for (let k = 0; k < 61; k++) {
				if (i === 0 && j === 0 && k === 0) continue;

				let min = 10000;

				// 점화식 적용
				for (let l = 0; l < 6; l++) {
					let [nx, ny, nz] = [i - dir[l][0], j - dir[l][1], k - dir[l][2]];

					if (nx < 0) nx = 0;
					if (ny < 0) ny = 0;
					if (nz < 0) nz = 0;

					min = Math.min(min, dp[nx][ny][nz] + 1);
				}

				dp[i][j][k] = min;
			}
		}
	}

	return dp[x][y][z];
};

console.log(solution(input));