백준 - N과 M (2) : 15650번

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

15650번: N과 M (2)

 

N과 M(1)문제 풀이 참고바람. (https://coding-gongboo.tistory.com/9?category=829643)

 

N과 M(1) 과의 차이점은 "고른 수열은 오름차순이어야 한다"는 점이다.

이를 위해서 현재 선택된 수 보다 1개 높은 위치의 수를 부터 수열을 만들어 나가야 한다.

이를 위해서 NM2(재귀함수)에 start해야 할 위치를 인자로 넘겨주는 부분이 수정되었다.

 

그리고 항상 다음 수를 대상으로 수열을 만들어 나가기 때문에 중복체크를 위한 included배열은 필요없다.

 

#include <bits/stdc++.h>

using namespace std;
//bool included[10]; //중복 체크
vector <int> nm;
void NM2(int, int, int);

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

void NM2(int s, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
   
    for (int i = s; i <= n; i++) {
        //if (!included[i]) {
            //included[i] = true;
            nm.push_back(i);
            NM2(i + 1, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
            nm.pop_back();
            //included[i] = false;
        //}
    }
}

 

두번째 풀이

각 수들을 포함 하거나 또는 포함 하지않으면서 다음수로 넘어가는 형태

 

#include <bits/stdc++.h>
using namespace std;
vector <int> nm;
void NM2(int level, int n, int m);

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

void NM2(int level, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    if (level > n) return;
    nm.push_back(level);
    NM2(level + 1, n, m);
    nm.pop_back();
    NM2(level + 1, n, m);
}

 

세번째 풀이

배열을 사용해서 결과값을 저장한 위치에 해당하는 index 인자를 관리해주고,

오름차순을 위해 다음 수를 지정해주는 start를 관리해 주는 형태

 

#include <bits/stdc++.h>
using namespace std;
int res[10];
void go(int index, int start, int n, int m);

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

void go(int index, int start, int n, int m) {
    if (index == m) {
        for (int i = 0; i < m; i++) {
            cout << res[i];
            if (i != m - 1) cout << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i = start; i <= n; i++) {
        res[index] = i;
        go(index + 1, i + 1, n, m);
    }
}