[伯俊/c+]15649号:NとM(1)

1701 ワード
Bruth Force テキストリンク
質問リンク-https://www.acmicpc.net/problem/15649

[質問]



[回答]


[再帰関数で解くことができるBroutForce問題の種類]
  • 順序に関する問題->N個の問題からM個を抽出する際に順序が重要な問題
  • 時間複雑度:N!
  • の選択に関する質問->N個のオプションからM個を選択した場合、一部を選択するか選択しないかを選択します.
  • 時間複雑度:2^N(Nオプション共有)
    • [回答]
  • この問題はN問題の中からM問題を選び、順序が違うと数列が違うので順序に関するBroutforce問題です.
  • 列の位置によって条件が異なるため、「位置」は関数のパラメータとして使用する必要があります.
    -位置によって条件が違う
    ->たとえば、1番の位置が4の場合、2番の位置は4ではなく、2番の位置が3の場合、3番の位置は3、4ではありません.(これは前の位置に依存するため、次の位置に到達可能な数の条件が異なる)

  • check[i]:iを使用する場合はtrue、そうでない場合はfalse

  • arr[]:格納配列

  • func(index,n,m)関数の役割:インデックスの1番目の数を決定します.

  • この問題の時間的複雑さ:N(N-1)…*1=N!

    • [コード]

    //15649. N과 M (1)
#include <iostream>
using namespace std;

bool check[10];
int arr[10];

void func(int index,int n,int m){
    if(index>m){
    // 수열 출력 부분
    for(int i=1; i<=m; i++){
        cout<<arr[i]<<" ";
    }
    //한번의 출력이 끝나면 줄바꿈 해주기
    cout<<"\n";
    return;
    }

    for(int i=1;i<=n; i++){
        if(check[i])
        continue;

        check[i]=true;
        arr[index]=i;
        func(index+1,n,m);
        check[i]=false;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    
    cin>>n>>m;
    func(1,n,m);
}
    プログラマ[レベル1]起動パスワード
    [Baekjoon] 1644. 少数連続[G 3]