22 asked

1

음..

이게 순열안에다가 재귀함수를 넣었는데... 보통은 순열을 재귀함수로 하거나 재귀함수로 할 걸 순열로 하거나 이러거든용... 이걸 보통은 같이 넣지는 않아요.

또한, 틀린 부분이 몇개 있는데요. 주석 달았습니다. 참고부탁드려요.

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

int n;
int num;
vector<int> scv;

int atk[] = {9, 3, 1};
int res = 1e9;

vector<int> collect() {
	vector<int> tmp;
	//이거 scv가 0이 되는 것은 왜 고려가 안되어있죠? 
	for (int i=0; i<scv.size(); i++) {
		if (scv[i] > 0) tmp.push_back(i);
	}
	return tmp;
}

vector<int> copySCV() {
	vector<int> tmp;
	//오마이갓.. 이걸 전역변수로 한다?? scv를 전역변수로? 
	for (int i : scv) {
		tmp.push_back(i);
	}
	return tmp;
}

void bt(int cnt) { 
//살아있는 scv를 모은다. 
	vector<int> candi = collect();
	// 다죽었다면 cnt 중 최솟값 
	if (candi.size() == 0) {
		res = min(res, cnt);
		return;
	}
	
	// 살아있는 scv의 순열을 만든다.  
	do {
		//이 scv로 부터 복사본을 만든다. 
		// 근데 전역변수를 기반으로 한다구요> candi를 기반으로 해야 되는거 아니에요? 
		vector<int> old = copySCV();
		for (int i=0; i<3; i++) {
			if (i >= candi.size()) break;
			scv[candi[i]] -= atk[i];
		}
		bt(cnt+1);
		scv = old;
		
	} while (next_permutation(candi.begin(), candi.end()));
}

int main() {
	
	cin >> n;
	for (int i=0; i<n; i++) {
		cin >> num;
		scv.push_back(num);
	}
	
	bt(0);
	cout << res << "\n";
	
	return 0;
}

0

주석을 보고 제가 얼마나 이상하게 짰는지 알 수 있었습니다. collect 함수에 전역변수를 쓴 것이 정말 치명적이네요..

scv가 0이 되는 부분을 제외한 이유는 체력이 0 또는 그 이하로 내려가면 파괴된다는 부분 때문입니다! 살아 있는 scv의 인덱스만을 모아야 해서요.

다만 저 코드의 잘못된 점을 다 고치더라도 시간제한을 통과할 수 없다는 사실도 알게 되었습니다. 코드를 고친 다음 마지막 테스트케이스를 돌려봤는데 5분이 지나도 연산이 끝나지 않더군요.. 메모이제이션을 해야 할 것 같은데 저 코드에서는 너무 복잡해질 것 같습니다. BFS 방식을 충분히 이해하고 비슷한 유형이 나왔을 때 떠올릴 수 있도록 하겠습니다.

답변 감사합니다!!