[프로그래머스 C++] 혼자 놀기의 달인

https://school.programmers.co.kr/learn/courses/30/lessons/131130

문제의 설명을 간단하게 설명하자면 다음과 같다.

1. 1 ~ 100까지의 숫자중 원하는 숫자보다 작은 카드를 전부 골라 각각 상자에 넣는다.
2. 그 상자에 1부터 시작하는 인덱스 값을 부여한다.
3. 상자를 열어 그 안에 있는 카드에 적혀 있는 인덱스의 상자로 이동한다
4. 이미 열려있는 상자에 도달할 때 까지 3번을 반복한다.
5. 도달하면 지금까지 열었던 상자를 하나의 그룹으로 정한다.
6. 그룹이 2개 나올때 까지 진행하여 각 그룹에 속해있는 상자의 갯수를 곱한다.

이를 진행하면서 최대로 나올 수 있는 값을 구하는 문제이다.

---

입력으로 주어진 cards에서 시작할 수 있는 모든 값을 시도해보는 방법으로 구현하였다.

각 시도마다 재귀형식으로 구현하여 값을 구했다.

 

상자를 열었는지 확인하는 open vector를 만들어 그 벡터를 확인하면서 count를 진행하였고, 하나라도 값이 남아있다면 다시 재귀형식으로 실행하여 count값에 재귀로 구해진 최댓값을 다시 곱하였다.

#include <string>
#include <vector>

using namespace std;

int score(vector<int> cards, vector<bool> open, int i, int time) {
    int idx = i;
    int count = 0;
    
    while(true) {
        if (!open[idx]) {
            open[idx] = true;
            idx = cards[idx] - 1;
            count++;
        }
        else
            break;
    }
    
    if (count >= cards.size())
        return 0;
    else if (time == 2)
        return count;
    
    int max = 0;
    
    for(int i = 0; i < cards.size(); i++) {
        if (!open[i]) {
            idx = i;
            
            int sum = score(cards, open, idx, 2);
        
            if (max < sum)
                max = sum;
        }
    }

    return count * max;
}

int solution(vector<int> cards) {
    int answer = 0;
    
    vector<bool> open;
    
     for (int i = 0; i < cards.size(); i++) {  
         open.push_back(false);
     }
    
    for (int i = 0; i < cards.size(); i++) {    
        int sum = score(cards, open, i, 1);
        if (answer < sum)
            answer = sum;
    }
    
    return answer;
}