[BOJ 12869] 뮤탈리스크

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

12869번: 뮤탈리스크

 

- 문제 요약

 

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다.

수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다.

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

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

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다.

한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

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

 

 

- 알고리즘 정리

 

재귀 DP를 사용해서 풀었습니다.

DP 배열의 정의는 아래와 같습니다.

DP[a][b][c] : 체력이 a, b, c인 SCV를 파괴하기 위한 최소 공격 횟수

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 61
int n,dp[MAX][MAX][MAX],arr[3];

int f(int a,int b,int c){
	if(a<0){
		return f(0,b,c);	
	}
	if(b<0){
		return f(a,0,c);	
	}
	if(c<0){
		return f(a,b,0);	
	}
	if(a==0&&b==0&&c==0){
		return 0;
	}
	int &result=dp[a][b][c];
	if(result!=-1){
		return result;
	}
	result=987654321;
	result=min(result,f(a-9,b-3,c-1)+1);
	result=min(result,f(a-9,b-1,c-3)+1);
	result=min(result,f(a-3,b-9,c-1)+1);
	result=min(result,f(a-1,b-9,c-3)+1);
	result=min(result,f(a-3,b-1,c-9)+1);
	result=min(result,f(a-1,b-3,c-9)+1);
	return result;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n;
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	cout<<f(arr[0],arr[1],arr[2]);
}

코드 제출 결과