백준 12869 c++ "뮤탈리스크" -PlusUltraCode-

https://www.acmicpc.net/problem/12869

 

[필자 사고]

동적프로그래밍 문제이다.

처음으로 탑다운 방식으로 문제를 해결한 문제이다.

약간의 나의 사고를 여기다 적어 보겠다.

초기 dp접근했을 때 값은 다 없다.

만약 다 없다고 하면 최대값을 넣는다.

그리고 가야할 구간을 적용시킨다.

그런데 만약 값이 -1이 아니라면 return 으로 해당 값을 반환한다.

이미 값이 결정됐따는 의미다.

 

그리고 초기에 if문을 이용하여 범위 검증을 통해 완수한다.

탑다운 방식은 아직 익숙치 않아서 다소 어려움이 있었다.

 

 

아래는 자세한 코드 해설이다.

[코드 해설]

2. 입력 처리

첫 번째 줄에는 몬스터의 개수를 나타내는 정수 NNN이 입력된다. 두 번째 줄에는 각 몬스터의 체력이 주어지며, 최대 3마리까지만 존재하기 때문에 배열을 사용하여 저장한다. 입력받지 않은 몬스터의 체력은 기본적으로 0으로 처리된다.

---

3. 동적 계획법을 위한 배열 초기화

각 체력 상태에서의 최소 공격 횟수를 저장하기 위해 3차원 배열을 사용한다. 이 배열은 특정한 체력 조합이 등장했을 때 중복 연산을 방지하기 위해 활용되며, 아직 방문하지 않은 상태는 -1로 초기화한다.

---

4. 가능한 공격 조합 정의

한 번의 공격은 세 마리 몬스터의 체력을 감소시키는데, 총 6가지의 공격 조합이 존재한다. 각각의 공격 조합은 큰 피해를 주는 몬스터가 다를 뿐, 전체적으로 동일한 피해 패턴을 따른다. 이를 미리 저장해 두어 반복적인 연산을 줄인다.

---

5. 최소 공격 횟수를 구하는 재귀적 DP 함수

각 몬스터의 체력 상태를 나타내는 세 개의 변수를 이용하여 최소 공격 횟수를 계산한다.
먼저, 모든 몬스터의 체력이 0이 되었을 경우 공격을 더 이상 할 필요가 없으므로 0을 반환한다.
만약 체력이 0보다 작아지는 경우가 있다면, 해당 체력을 0으로 조정하여 불필요한 연산을 줄인다.
이미 계산된 상태라면 저장된 값을 반환하여 중복 연산을 방지한다.
각 공격 조합을 적용한 후, 가능한 모든 경우를 탐색하여 최소 공격 횟수를 구한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cstring>

using namespace std;

int N;
int dp[61][61][61];
int hp[3];
vector<vector<int>> attack = {
	{9,3,1},
	{9,1,3},
	{3,9,1},
	{3,1,9},
	{1,3,9},
	{1,9,3}
};

int solution(int x, int y, int z) {
	if (x == 0 && y == 0 && z == 0) return 0;
	else if (x < 0) return solution(0, y, z);
	else if (y < 0) return solution(x, 0, z);
	else if (z < 0) return solution(x, y, 0);

	int& res = dp[x][y][z];
	if (res != -1) return res;
	res = INT_MAX;
	for (int i = 0; i < 6; i++) {
		res = min(res, solution(x - attack[i][0], y - attack[i][1], z - attack[i][2]) + 1);
	}
	return res;
}

int main(void) {
	cin >> N;
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < N; i++)cin >> hp[i];
	cout << solution(hp[0], hp[1], hp[2]) << '\n';
}