[Back Tracking] 백준 15649번 - N과 M(1)

 

N과 M모두 8이하의 수이기 때문에 

최대 8중 for문으로 돌아간다.

8^8 < 10^8 이므로 1초 안에 해결 가능! -> Brute Force로 풀 수 있는 문제이다

 

가변하는 여러 겹의 for를 어떻게 만들것인가?

   -> 재귀함수 사용한다

 

choose[] = 이미 선택된 것을 나타내는 배열

answer[] = 답을 순서대로 출력하기 위해서 저장해 놓는 배열

 

만약 세개를 다 선택했다면 loop를 나간다

나갈때, 답을 출력한다.

 

loop를 나가고 나서 다시 2단계로 돌아올 때 끝난 과정의 3단계에서 choose된 것을 false로 바꾸어 준다

추후 다른 2단계에서 선택된 경우에서 써야 한다 (같은 단계에서는 어차피 for문이 다음으로 넘어가기 때문에 상관 없다)

 

 

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
#define endl '\n'

int M, N, min_num, cnt1, cnt2;
char input;
bool choosed[10];
int answer[10];

void loop(int choose){
    if(choose == M+1){
        for(int i=1; i<=M; i++){
            cout<<answer[i]<<' ';
        }
        cout<<endl;
        return;
    }
    for(int i=0; i<N; i++){
        if(choosed[i]==true)
            continue;
        else{
            choosed[i]=true;
            answer[choose] = i+1;
            loop(choose+1);
            choosed[i]=false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin>>N>>M;

    for(int i=0; i<8; i++){
        choosed[i]=false;
    }
    loop(1);
    
}