[백준] 2668번 - 숫자 고르기

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

이 문제는 그냥 일반적인 백트래킹으로 풀 수 없는 문제다.

자세히 말하면 target 으로 하는 갯수를 for로 돌면서 그 갯수를 만족하는 선택을 했을 때 조건을 확인하는 백트래킹 방식으로 풀면 시간 초과가 된다. N이 100이고 선택하는 것이 50개만 되더라도 100C50 = 9.332622e+157이다. 한 케이스에 대해서도 이렇게나 걸리니까 당연히 제한시간 1초에 동작하지 못한다.

 

아래는 그냥 일반적인 백트래킹 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
int N;
int target;
bool foundAnswer = false;
vector<int> up, down;
 
void dfs(int idx, vector<int> upmaking, vector<int> downmaking){
    if (idx > N - 1) return;
    if (N - idx + upmaking.size() < target) return;
    if (upmaking.size() == target && downmaking.size() == target){
        bool allSame = true;
        sort(upmaking.begin(), upmaking.end());
        sort(downmaking.begin(), downmaking.end());
        for (int i = 0; i < upmaking.size(); i++){
            if (upmaking[i] != downmaking[i]){
                allSame = false;
                break;
            }
        }
        if (allSame){
            cout << upmaking.size() << '\n';
            for (int i = 0; i < upmaking.size(); i++){
                cout << upmaking[i] << '\n';
            }
            foundAnswer = true;
            exit(0);
        }
    }
    upmaking.push_back(up[idx]);
    downmaking.push_back(down[idx]);
    dfs(idx + 1, upmaking, downmaking);
    
    upmaking.pop_back();
    downmaking.pop_back();    
    dfs(idx + 1, upmaking, downmaking);    
    return ;
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++){
        up.push_back(i + 1);
    }
    int ele;
    for (int i = 0; i < N; i++){
        cin >> ele;
        down.push_back(ele);
    }
    // up, dwon에 각각 숫자들 넣어둠.
    for (int num = N; num >= 1; num--){
        target = num;
        vector<int> upm, downm;
        dfs(0, upm, downm);
        if (foundAnswer) break;
    }
    return 0;
}

 

더더군다나 스택 메모리도 부족할 수 있다.

 

그러면 어떻게 풀어야 했을까?

서치를 해본 결과 사람들은 대부분 사이클을 고려한 문제풀이를 했다.

 

#include<iostream>
#include<algorithm>
using namespace std;
 
 
int N;
 
int ans[101];
int fin[101];
int map[101];
int visited[101];
int cnt = 0 ;
 
void dfs(int n)
{
    int i;
 
    visited[n] = 1 ;
 
    if(visited[ map[n] ] == 0 )
    {
        dfs( map[n] );
 
    }
 
    else if( fin[map[n]] == 0)
    {
        ans[cnt++] = n;
        
        for( i = map[n] ; i !=n ; i = map[i] )
        ans[cnt++] = i;
 
 
    }
 
 
    fin[n] = 1;
 
 
 
}
 
 
 
 
int main()
{
    int i,j;
 
    cin >> N ;
 
    for(  i =1 ; i<= N ; i++)
        cin >>map[i];
 
 
 
 
    for(  i =1 ; i<= N ; i++)
    {
        if(visited[i]) continue;
        
            dfs(i);
 
    }
 
 
    sort(ans,ans+cnt);
 
    cout << cnt << "\n";
    for( i = 0 ;i<cnt; i++)
    cout << ans[i] << "\n"; 
 
 
    return 0;
}