[BOJ] N과 M

최준혁·2023년 11월 5일
ps

N과 M 시리즈

재귀함수를 연습하기 좋은 문제집이자 완전 탐색의 기본이 되는 문제들이다.

N과 M (1) - nPm 완전탐색


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> picked(m,-1);
    vector<ll> visited(n,false);
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<x+1<<' ';
            cout<<'\n';
            return;
        }
        for(ll i=0;i<n;i++){
            if(!visited[i]){
                picked[idx]=i; visited[i]=true;
                f(idx+1);
                visited[i]=false;
            }
        }
    };
	f(0);
    return 0;
}

N과 M (2) - nCm 완전탐색


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> picked(m,-1);
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<x+1<<' ';
            cout<<'\n';
            return;
        }
        ll i=(idx?picked[idx-1]+1:0);
        for(;i<n;i++){
            picked[idx]=i;
            f(idx+1);
        }
    };
	f(0);
    return 0;
}

0-1 순열

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ll n,m; cin>>n>>m;
    vector<bool> pick(n); 
    for(ll i=0;i<n;i++) pick[i]=(i<m?0:1);
    do{
        vector<ll> picked;
        for(ll i=0;i<n;i++){
            if(!pick[i]) picked.push_back(i);
        }
        for(ll x:picked) cout<<x+1<<' ';
        cout<<'\n';
    }while(next_permutation(pick.begin(),pick.end()));
    return 0;
}

N과 M (3) - nm{n}^{m} 완전탐색


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> picked(m,-1);
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<x+1<<' ';
            cout<<'\n';
            return;
        }
        for(ll i=0;i<n;i++){
            picked[idx]=i;
            f(idx+1);
        }
    };
	f(0);
    return 0;
}

N과 M (4) - nHm 완전탐색


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> picked(m,-1);
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<x+1<<' ';
            cout<<'\n';
            return;
        }
        ll i=(idx?picked[idx-1]:0);
        for(;i<n;i++){
            picked[idx]=i;
            f(idx+1);
        }
    };
	f(0);
    return 0;
}

5번~8번: 1~N 중에서 뽑는 것 -> N개의 자연수 중에서 뽑는 것

N과 M (5) - N과 M (1)의 확장


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll& x:A) cin>>x;
    sort(all(A));
    vector<ll> picked(m,-1);
    vector<bool> visited(n,false);
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<A[x]<<' ';
            cout<<'\n';
            return;
        }
        for(ll i=0;i<n;i++){
            if(!visited[i]){
                picked[idx]=i; visited[i]=true;
                f(idx+1);
                visited[i]=false;
            }
        }
    };
	f(0);
    return 0;
}

N과 M (6) - N과 M (2)의 확장


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll& x:A) cin>>x;
    sort(all(A));
    vector<ll> picked(m,-1);
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<A[x]<<' ';
            cout<<'\n';
            return;
        }
        ll i=idx?picked[idx-1]+1:0;
        for(;i<n;i++){
            picked[idx]=i;
            f(idx+1);
        }
    };
	f(0);
    return 0;
}

0-1 순열

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll i=0;i<n;i++) cin>>A[i];
    sort(all(A));
    vector<bool> pick(n); 
    for(ll i=0;i<n;i++) pick[i]=(i<m?0:1);
    do{
        vector<ll> picked;
        for(ll i=0;i<n;i++){
            if(!pick[i]) picked.push_back(A[i]);
        }
        for(ll x:picked) cout<<x<<' ';
        cout<<'\n';
    }while(next_permutation(pick.begin(),pick.end()));
    return 0;
}

N과 M (7) - N과 M (3)의 확장


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll& x:A) cin>>x;
    sort(all(A));
    vector<ll> picked(m,-1);
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<A[x]<<' ';
            cout<<'\n';
            return;
        }
        for(ll i=0;i<n;i++){
            picked[idx]=i;
            f(idx+1);
        }
    };
	f(0);
    return 0;
}

N과 M (8) - N과 M (4)의 확장


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll& x:A) cin>>x;
    sort(all(A));
    vector<ll> picked(m,-1);
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<A[x]<<' ';
            cout<<'\n';
            return;
        }
        ll i=idx?picked[idx-1]:0;
        for(;i<n;i++){
            picked[idx]=i;
            f(idx+1);
        }
    };
	f(0);
    return 0;
}

9번~12번: N개의 자연수는 모두 다른 수이다 -> N개의 자연수 중 같은 것이 존재할 수 있다

N과 M (9)


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll& x:A) cin>>x;
    sort(all(A));
    vector<ll> picked(m,-1);
    vector<ll> visited(10000+1,0);
    for(ll x:A) visited[x]++;
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<x<<' ';
            cout<<'\n';
            return;
        }
        for(ll x:A){
            if(visited[x]){
                picked[idx]=x; visited[x]--;
                f(idx+1);
                visited[x]++;
            }
        }
    };
	f(0);
    return 0;
}

N과 M (10)


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll& x:A) cin>>x;
    sort(all(A));
    vector<ll> picked(m,-1);
    vector<ll> visited(10000+1,0);
    for(ll x:A) visited[x]++;
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<x<<' ';
            cout<<'\n';
            return;
        }
        ll mx=idx?picked[idx-1]:0;
        for(ll x:A){
            if(x>=mx&&visited[x]){
                picked[idx]=x; visited[x]--;
                f(idx+1);
                visited[x]++;
            }
        }
    };
	f(0);
    return 0;
}

N과 M (11)


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll& x:A) cin>>x;
    sort(all(A));
    vector<ll> picked(m,-1);
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<x<<' ';
            cout<<'\n';
            return;
        }
        for(ll x:A){
            picked[idx]=x;
            f(idx+1);
        }
    };
	f(0);
    return 0;
}

N과 M (12)


백트래킹

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

int main(){
    ll n,m; cin>>n>>m;
    vector<ll> A(n); 
    for(ll& x:A) cin>>x;
    sort(all(A));
    vector<ll> picked(m,-1);
    sort(A.begin(),A.end());
    A.erase(unique(A.begin(),A.end()),A.end());
    function<void(ll)> f = [&](ll idx){
        if(idx==m){
            for(ll x:picked) cout<<x<<' ';
            cout<<'\n';
            return;
        }
        ll mx=idx?picked[idx-1]:0;
        for(ll x:A){
            if(x>=mx){
                picked[idx]=x;
                f(idx+1);
            }
        }
    };
	f(0);
    return 0;
}
profile
최준혁
이전 포스트

C/C++ 기본 템플릿 - PS를 위한

다음 포스트

Fund Me

0개의 댓글