12869 뮤탈리스크★

12869 뮤탈리스크★

각각의 SCV를 때릴 때 체력을 확인해야 하므로 완전탐색을 사용해야 함

1. 공격 횟수의 최솟값
   • 전역변수에 저장하여 모든 SCV의 체력이 0이거나 0보다 작을 때, 값을 갱신

2. SCV의 체력
   • 함수의 파라미터에 저장
   1. 체력 감소
      • 함수를 호출할 때마다 감소

3. 어떤 SCV를 먼저 때릴 것인가?
   • 조합 문제로 바꿔서 생각해볼 수 있음.

---

부족했던 점

• 이전에 비슷한 문제를 풀었던 적이 있었나?
  • 입력의 범위가 작은 완전탐색 문제
  • 중복된 부분문제의 답을 저장하는 문제

• 이 사람의 풀이가 명쾌하다.
  • https://jason9319.tistory.com/290
  • https://jason9319.tistory.com/category/알고리즘 관련/알고리즘%26이론?page=1

1. 가장 단순한 완전 탐색부터 시도해보고 시간 단축을 고민했어야 했다.
   • 입력의 범위가 작기 때문이다.

2. 부분문제의 결과가 중복되서 사용된다.
   • 부분문제의 결과가 중복되는 이유

     • 예를 들어, scv1, 2, 3의 체력을 각각 1, 3, 9라 하면 모든 경우를 탐색할 때 중복해서 탐색하게 된다!
   • 메모이제이션 사용이 가능하다!

   ⇒ 부분문제의 답을 저장하기 위해 배열을 사용한걸로 보인다.

---

• 실패한 코드

  문제 원인 : 시간이 너무 오래걸린다.

  → 중복된 부분 문제가 많다.

  #include <iostream>
  #include <algorithm>
  using namespace std;
  int N;
  int result = 999999999;
  void dfs(int attack, int scv1, int scv2, int scv3)
  {
  	if (scv1 <= 0 && scv2 <= 0 && scv3 <= 0) {
  		result = min(result, attack);
  		return;
  	}
  	dfs(attack + 1, scv1 - 9, scv2 - 3, scv3 - 1);
  	dfs(attack + 1, scv1 - 9, scv2 - 1, scv3 - 3);
  	dfs(attack + 1, scv1 - 3, scv2 - 9, scv3 - 1);
  	dfs(attack + 1, scv1 - 3, scv2 - 1, scv3 - 9);
  	dfs(attack + 1, scv1 - 1, scv2 - 3, scv3 - 9);
  	dfs(attack + 1, scv1 - 1, scv2 - 9, scv3 - 3);
  }
  int main()
  {
  	int scv[3] = { 0, };
  	cin >> N;
  	for (int i = 0; i < N; i++) {
  		cin >> scv[i];
  	}
  	dfs(0, scv[0], scv[1], scv[2]);
  	printf("%d\n", result);
  	return 0;
  }

• 성공한 코드

  #include <iostream>
  #include <cstring>
  #include <algorithm>
  using namespace std;
  #define INF 987654321
  int N;
  int dp[61][61][61];
  int bf(int scv1, int scv2, int scv3)
  {
  	if (scv1 <= 0 && scv2 <= 0 && scv3 <= 0) {
  		//SCV가 모두 죽음
  		return 0;
  	}
  	int& ret = dp[scv1][scv2][scv3];
  	//이미 답을 알고 있는 부분문제면, 바로 반환한다.
  	if (ret != -1) return ret;
  	//계산하지 않은 부분문제이면, -1값으로 저장되지 않도록 큰 값을 저장한다.
  	ret = INF;
  	ret = min(ret, bf(max(0, scv1 - 9), max(0, scv2 - 3), max(0, scv3 - 1)) + 1);
  	ret = min(ret, bf(max(0, scv1 - 9), max(0, scv2 - 1), max(0, scv3 - 3)) + 1);
  	ret = min(ret, bf(max(0, scv1 - 3), max(0, scv2 - 1), max(0, scv3 - 9)) + 1);
  	ret = min(ret, bf(max(0, scv1 - 3), max(0, scv2 - 9), max(0, scv3 - 1)) + 1);
  	ret = min(ret, bf(max(0, scv1 - 1), max(0, scv2 - 3), max(0, scv3 - 9)) + 1);
  	ret = min(ret, bf(max(0, scv1 - 1), max(0, scv2 - 9), max(0, scv3 - 3)) + 1);
  	return ret;
  	
  }
  int main()
  {
  	memset(dp, -1, sizeof(dp));
  	int scv[3] = { 0, };
  	cin >> N;
  	for (int i = 0; i < N; i++) {
  		cin >> scv[i];
  	}
  	
  	printf("%d\n", bf(scv[0], scv[1], scv[2]));
  	return 0;
  }