프로그래머스 레벨2 <혼자 놀기의 달인> C++ 풀이

정답을 만들어낼 수 있는 모든 조건의 경우의 수를 다 탐색해보는 문제였습니다. 문제가 길긴 하지만 어려운 부분은 딱히 없고 그대로 구현만 하면되는데, SoloGame 함수의 인자로 cards를 넘길 때 참조로 넘기게 되면 cards의 변화가 계속 반영되기 때문에 참조가 아닌 일반적인 복사 형태로 넘겨야합니다. 그래야 경우의 수마다 서로 다른 cards를 참조해서 정확한 답을 도출할 수 있습니다.

 

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
vector<int> res;
 
void SoloGame(int idx,vector<int> cards,int count)
{
    int cnt = count;
    int curCnt = 0;
    int curIdx = idx;
    
    while(true)
    {
        int curVal = cards[curIdx];
        
        if (curVal != 0)
        {
            cards[curIdx] = 0;
            curIdx = curVal-1;
            curCnt++;
        }
        else
        {
            break;
        }        
    }
    
    
    
    if (cnt != 0 || curCnt + cnt == cards.size())
    {
        res.push_back(cnt * curCnt);
        return;
    }
        
    
    for (int i=0;i<cards.size();i++)
    {
        if (cards[i] != 0)
            SoloGame(i,cards,curCnt);
    }
    
    
}
 
int solution(vector<int> cards) {
    
    for (int i=0;i<cards.size();i++)
    {
        SoloGame(i,cards,0);
    }
    sort(res.begin(),res.end());
        
    return res[res.size()-1];
}