3-E 질문있습니다!

왜 메모리 초과가 나는지 잘 모르겠습니다 ㅠㅠ

http://boj.kr/3f4ea7f3a10b47edae0daa68dd2cf90d

그리고 선생님 코드와 무슨차이인지도 잘 모르겠습니다...

결국엔 6개의 경우의 수가 계속 추가 되는데

겹치는게 있을시 6개보다 적은 경우의 수가 들어간다

인데...

도저히 모르겠어요 ㅠㅠㅠ

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
using namespace std;

int N, ret;
vector<int> scv;
queue<pair<vector<int>, int>> q;
set<vector<int>> visited;


vector<int> Damage(vector<int> v)
{
	int divide = 1;
	for (int i = 0; i < v.size(); i++)
	{
		v[i] -= 9 / divide;
		divide *= 3;
	}

	return v;
}

void Mutalisk()
{
	while (q.size())
	{
		vector<int> v = q.front().first;
		int cnt = q.front().second;
		q.pop();

		v = Damage(v);
		sort(v.begin(), v.end(), greater<int>());
		for (int i = (int)v.size() - 1; i >= 0; i--)
			if (v[i] <= 0)
				v.pop_back();

		if (v.size() == 0)
		{
			ret = cnt + 1;
			return;
		}

		do
		{
			q.push({ v, cnt + 1 });
			auto it = visited.insert(v);
			if (it.second == false)
				continue;
		} 
		while (prev_permutation(v.begin(), v.end()));
	}
}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		scv.push_back(0);
		cin >> scv[i];
	}

	sort(scv.begin(), scv.end(), greater<int>());

	do 
	{
		q.push({ scv, 0 });
	}
	while (prev_permutation(scv.begin(),scv.end()));

	Mutalisk();

	cout << ret;

	return 0;
}

안녕하세요 가인님 ㅎㅎ

일단 이코드는 고쳐야할 점들이 몇가지 있습니다.

순열: SCV의 상태 - 순열을 생성하기 위해 prev_permutation을 사용하는 것은 조금은 비효율적입니다.

데미지 계산: pop_back() 등을 기반으로 하는데.. 너무 복잡합니다.

대표적으로 이부분이 문제인데요.

		do
		{ 
			q.push({ v, cnt + 1 });
			auto it = visited.insert(v);
			if (it.second == false)
				continue;
		} 
		while (prev_permutation(v.begin(), v.end()));

일단 이 코드는 continue를 해도 무조건 permutation이 잡히게 됩니다. 즉, 매번 v.size()!의 순열이 동작하게 되는 것이기 때문에 조금은 비효율적이라고 볼 수 있습니다.
대미지를 고정시키고 scv를 순회하는 것은 좋은 생각입니다만.. 이부분에 대한 로직이 좀 이상합니다.

대미지를 준 상태 -> 해당 정점 방문했는지 체크하는 식으로 해야 하는데 이로직 기반으로는 그게 어렵습니다. 만약 그렇게 하더라도 좀 복잡해지는게

대미지를 주고 원복해야 하는데 해당 부분에 있어서 그냥 -가 아니라 max를 기반으로 했기 때문에 이렇게 코드를 짠다고 해도 해당 부분에 대한 로직의 수정이 필요합니다.

일단은 제가 이렇게 다듬어봤는데요. 참고 부탁드립니다. (답은 아닙니다. )

#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
using namespace std;

int N, ret;
vector<int> scv;
queue<pair<vector<int>, int>> q;
set<vector<int>> visited;
bool check(vector<int> v){
    for(int i : v){
        if(i != 0) return false; 
    }
    return true;
}
void Mutalisk()
{
    visited.insert(scv);
    q.push({scv, 1});
    while (q.size())
    {
        vector<int> v = q.front().first; 
        int cnt = q.front().second; 
        q.pop(); 
        if(check(v)){
            ret = cnt; 
            break;
        }     
        sort(v.begin(), v.end());
        do
        {  
            int j = 0; 
            for(int i : {9, 3, 1}){
                v[j] = max(0, v[j] - i);  
                j++;  
            } 
            const bool is_in = visited.find(v) != visited.end(); 
            if(is_in) continue; 
            visited.insert(v); 
            q.push({ v, cnt + 1 });
            //여기서 max를 고려한 수정이 더 필요함. - 원복
            int j = 0; 
            for(int i : {9, 3, 1}){
                v[j] = max(0, v[j] + i);  
                j++;  
            } 
        } 
        while (prev_permutation(v.begin(), v.end()));
    }
}

int main()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int temp; 
        cin >> temp; 
        scv.push_back(temp); 
    }
    if(scv.size() == 1){
        scv.push_back(0);
        scv.push_back(0);
    }else if (scv.size() == 2){
        scv.push_back(0);
    }
    sort(scv.begin(), scv.end()); 
    Mutalisk();
    cout << ret;

    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

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