[백준/C++] 15650번: N과 M (2)(S3)

문제

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

15650번: N과 M (2)

 

 

사용한 알고리즘

2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹

-> 백트래킹.
    가능한 모든 경우를 단순히 생성하는 문제이다.
    재귀로 상태를 전이시켜가며 문제를 풀어보자.

 

풀이

처음에는 숫자를 넣을 인덱스만 인자로 전달했었다. 
그렇게 하면 현재 넣을 숫자가 무엇인지 반복문을 돌면서 알아내야 한다.

따라서 필요한 상태는 현재 넣을 숫자와 현재 숫자를 넣을 인덱스라는 것을 알았고
인자로 그 두 가지를 전달했다.

각각 소스코드 1, 2에 첨부되어있다.

 

 

소스코드 1

#include <iostream>
typedef long long ll;
using namespace std;
int n,m;
int arr[10];

void solve(int k){ // arr[k]를 정해야함 
    if(k==m){ //m개(arr[0]~arr[m-1])를 다 정했으면 출력
        for(int i=0; i<m; i++) cout<<arr[i]<<" ";
        cout<<'\n';
        return;
    }
    for(int i=1; i<=n; i++){
        if(k!=0 && arr[k-1]>=i) continue; //오름차순 조건 불만족하면 스킵
        arr[k]=i;
        solve(k+1);
        arr[k]=0;
    }
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n>>m;
    solve(0);

    return 0;
}

 

소스코드 2 🌟

#include <iostream>
typedef long long ll;
using namespace std;
int n,m;
int arr[10];

void solve(int cur, int idx){ //현재 넣을 숫자, 현재 넣을 인덱스
    if(idx==m){ //m개(arr[0]~arr[m-1])를 다 정했으면 출력
        for(int i=0; i<m; i++) cout<<arr[i]<<" ";
        cout<<'\n';
        return;
    }
    if(cur==n+1) return; //모든 숫자 다 봤으면 리턴
    arr[idx]=cur;
    //idx에 cur넣을 경우
    solve(cur+1, idx+1);
    //idx에 cur을 넣지 않고 그 다음 값을 넣을 경우
    solve(cur+1, idx);
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin>>n>>m;
    solve(1,0);

    return 0;
}