백준 N과 M (3),(4) [c++]

N과M 3,4 실버 3

N과M 3

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다.

N과M 4

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

풀이

• 이전 N과M1,2와 유사한 문제인데 3은 중복허용, 4는 중복허용 + 비내림차순 출력이었다.
• 조건에 맞게 promising을 수정하니 쉽게 해결

코드

NM 3

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

queue <vector<int> > q;
int n, m;

void promising(vector<int> v)
{
    int size = v.size();

    if(size == m){
        //print & return;
        for(int i = 0; i < m; i++)
        {
            cout << v[i] << " ";
        }
        cout << "\n";
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        // int varified = 1;
        // for(int s = 0; s < size; s++){
        //     if(v[s] == i){
        //         varified = 0;
        //     }
        // }
        // if(varified == 1){
        //     vector<int> add(v);
        //     add.push_back(i);
        //     q.push(add);
        // }
        vector<int> add(v);
        add.push_back(i);
        q.push(add);
    }
}

int main(){
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        vector<int> v;
        v.push_back(i);
        q.push(v);
    }

    while(!q.empty()){
        int qsize = q.size();
        //cout << "q_size : " << qsize << endl;
        for(int i = 0; i < qsize; i++)
        {
            vector<int> t = q.front();
            q.pop();
            promising(t);

        }
    }
    
    return 0;
}

NM 4

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

queue <vector<int> > q;
int n, m;

void promising(vector<int> v)
{
    int size = v.size();

    if(size == m){

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

    }

    for(int i = 1; i <= n; i++)
    {
        // int varified = 1;
        // for(int s = 0; s < size; s++){
        //     if(v[s] == i){
        //         varified = 0;
        //     }
        //     if(v.back() > i){

        //     }
        // }
        // if(varified == 1){
        //     vector<int> add(v);
        //     add.push_back(i);
        //     q.push(add);
        // }

        if(v.back() <= i){
            vector<int> add(v);
            add.push_back(i);
            q.push(add);
        }

    }
}

int main(){
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        vector<int> v;
        v.push_back(i);
        q.push(v);
    }

    while(!q.empty()){
        int qsize = q.size();
        //cout << "q_size : " << qsize << endl;
        for(int i = 0; i < qsize; i++)
        {
            vector<int> t = q.front();
            q.pop();
            promising(t);

        }
    }
    
    return 0;
}

총평

• easy

• ps
• back-tracking