N과 M (1-5)(백준)

N과 M (1)

#15649 백준

풀이 생각 과정

중복 없이 M개를 고른 수열을 뽑으니

n 과 m 인풋을 받고, dfs에서 입력값과 m이 일치하면 출력,

그리고 if(!check[i])같은 bool 배열 조건문으로 중복을 지속적으로 체크(백트래킹)을 해줘야 함.

dfs(입력값 + 1) 로 재귀 함수 돌리기

 

코드

#include <iostream>
using namespace std;

int a[11];
bool check[11];
int n;
int m;

//Backtracking, Recursion, DFS

void dfs(int d){
    
    if (d == m){
        for (int i = 0; i < m; i++){
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }
    
    for (int i = 1; i <= n; i++){

        if(!check[i]){ //true false allocation 다지우면 SIGBUS
            check[i] = true;
            a[d] = i;
            dfs(d + 1);
            check[i] = false;
        }
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;

    dfs(0);
    
}

 

N과 M (2)

#15650 백준

풀이 생각 과정

1번과 나머지는 동일하다, 하지만 오름 차순이라는 조건이 있으므로 조건문 하나를 더 붙이거나, 변수 하나를 함수에 더 붙여야함.

c는 선택된 숫자들의 갯수로 정의하고, 선택된 숫자들이 m개면 결과를 출력해야함

그리고 재귀 돌때에는 포함할 경우(true) 와 포함하지 않을경우(false)를 모두 생각해야 하기때문에 true 일 경우에는 c+1 아닐 경우에는 c로 만들어줘야함 

코드

Optimal

#include <iostream>
using namespace std;

bool table[9];
int n, m;

void bt(int a, int b) {
    if (a == n + 1 && b != m) {
        return;
    }
    if (b == m) {
        for (int c = 1; c <= n; ++c) {
            if (table[c]) cout << c << ' ';
        }
        cout << '\n';
        return;
    }
    table[a] = true;
    bt(a + 1, b + 1);
    table[a] = false;
    bt(a + 1, b);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    bt(1, 0);
}

 

Suboptimal(설명은 코드 안에)

#include <iostream>
using namespace std;

int a[10];
bool check[10];
int n,m;

//References
// dfs 알고리즘 수도코드, 순열 가로, 세로 출력하기, s = a[t - 1] + 1 은 힌트를 얻어가며 도출


void dfs2(int t){

    if (t == m){
        for (int i = 0; i < m; i ++){
            cout << a[i] << ' ';
        }
        cout << '\n';
    }

    int s = 1;
    if (t > 0){
        s = a[t-1] + 1; 
        //t가 0 이상이면 a array 안에 있는 순열 숫자의 값 + 1 로 s를 정해줌으로써 루프 돌때 출력값 좌측 숫자보다 우측 숫자(좌 < 우)가 커지는걸 방지.
        //lets assume t = 0 and we start from 1. n = 4, m = 2.
        //possible elements from a[0] = 1,2,3,4
        //lets say pick 1 for a[0] since s = 1. In t == 1 ,we pick a # that is larger than 1, so when a[0] + 1, the result
        //becomes 2 and the choices left are 2,3,4. If we pick 2, then it will form 1, 2 and returns result as expected.
    }
    for (int j = s; j <= n; j++){
        if (!check[j]){
            check[j] = true;
            a[t] = j;
            dfs2(t + 1);
            check[j] = false;
            
        }
        
    }

}

int main(){

    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    dfs2(0);
}

 

N과 M (3)

#15651 백준

 

풀이 생각 과정

같은 수를 여러번 골라도 된다 했으니 if(!check[i]) 만 제거하고 그대로 하면 됨. true, false 지정도 상관없어짐. 

코드

#include <iostream>
using namespace std;

int arr[9];
bool use[9];
int n, m;
void backtrack(int t){

    if (t == m){
        for (int i = 0; i < m; i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++){
        //이번에는 중복도 허용, 그러하니 if !(use[i]) 를 제거시키는 접근.
        // -> use[i]가 false 인 애들만 고르지 않음. 따라서 중복 제거를 안하게됨.
        arr[t] = i;
        backtrack(t + 1);
    }

}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    backtrack(0);

}

 

N과 M (4)

#15652 백준

 

풀이 생각 과정

비내림차순으로 출력되야 하기때문에 그렇지 않은 경우들을 제외시켜야함.

코드

처음에는 생각이 잘 정리되지 않아 조건문 걸고 풀었는데, 지금은 n과 m 2번 풀이를 바탕으로 더 Optimal 하게 풀수있다.

Optimal 

#include <iostream>
using namespace std;
int n,m;
int arr[11];
int check[11];

void backtrack(int t, int s){

    if (t == m){
        for (int i = 0; i < m; i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = s; i <= n; i++){
        arr[t] = i;
        backtrack(t + 1, i); 
    }

}

int main(){
    cin >> n >> m;
    backtrack(0, 1);
}

Suboptimal

#include <iostream>

using namespace std;

int n,m;

int arr[11];

int check[11];

void backtrack(int t){

if (t == m){

for (int i = 0; i < m; i++){

cout << arr[i] << " ";

}

cout << "\n";

return;

}

int s = 1;

if (t > 0){

s = arr[t - 1]; // 2 1 3 1 3 2 같은 순서 방지(좌 > 우)..

}

for (int i = s; i <= n; i++){

// 중복허용

check[i] = true;

arr[t] = i;

backtrack(t + 1);

check[i] = false;

 

}

}

int main(){

cin >> n >> m;

backtrack(0);

}

 

N과 M (5)

#15654 백준

 

풀이 생각 과정

기존의 n과 m 문제들과 다른 방법으로 풀어내야함.

배열을 통해 밑에 한줄 입력을 받고, 그리고 중복을 허용 안하니 백트래킹으로 가지치기를 하고, a[t] = i 가 아닌 새로운 배열 받은걸 그대로 a[t]에 받아주면 된다.

 

코드 

#include <iostream>
#include <algorithm>
using namespace std;

int n,m;
int n1[11]; //새로운 입력이 나타났으므로 배열을 통해 받음
int a[11];
int check[11];
void bt(int t){
    
    if (t == m){
        for (int i = 0; i < m; i++){
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 0; i < n; i++){ //0으로 안바꾸면 둘째 줄 n개의 수중 가장 작은 수가 입력이 안되서 결과가 이상하게 나옴 
        if (!check[i]){
            a[t] = n1[i]; //n1안에 있는 애들로 순열 만드는거니까 i에서 n1[i]로 
            check[i] = true; //이건 a[i]의 check를 보는거니 i 인덱스로 고정
            bt(t + 1);
            check[i] = false;
        }
        }
    }

int main(){

    cin >> n >> m;

    for (int i = 0; i < n; i++){
        cin >> n1[i];
    }
    sort(n1, n1 + n); //없으면 내림차순으로 출력되서 sort가 이 풀이에선 꼭 필요
    bt(0);

}

 

N 과 M 시리즈는 더 있지만 입력의 차이라던지 그런것만 있고 문제 조건이 크게 변한다던지 하는것은 없어서 이정도 풀면 문제의 본질 정도는 파악한것 같다.