3-E 시간복잡도 질문

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-E

작성

266

http://boj.kr/b21ecf8f6e2b448294cf68f640e96624

9, 3, 1의 순열을 구할 생각을 못해서

scv의 순열을 턴마다 구한 뒤 백트래킹하는 방식으로 풀었습니다.

순열을 구하는 경우의 수는 턴당 최대 3! 이고 턴 횟수를 넉넉잡아서 100으로 생각해도 3! * 100 정도밖에 안 된다고 생각 -> 백트래킹

이런 사고의 흐름을 거쳤는데 시간초과가 난 걸 보면 시간복잡도 계산을 이상하게 한 것 같습니다.

이 문제에서 만약 제 방법대로 풀었을 때 시간복잡도를 제대로 계산하려면 어떻게 해야 할까요?

C++코테 준비 같이 해요!

답변 2

큰돌

지식공유자

음..

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

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

#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;
}

yeon _leaf

질문자

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

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

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

답변 감사합니다!!

인프런 커뮤니티 질문&답변

3-E 시간복잡도 질문