15650 N과 M (2)

N과 M (1)

앞의 문제와 차이라면 promising 부분..

오름차순인지 확인하는 걸 추가했다. 

#include <iostream>
#include <vector>

using namespace std;

void    print_vector(int m, vector<int> v)
{
    for (int i = 0; i < m; i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}

bool    promising(int index, vector<int> v)
{
    for (int i = 1; i <= index; i++)
    {
        if (v[i - 1] > v[i])
            return (false);
        for (int j = 0; j < i; j++)
        {
            if (v[i] == v[j])
                return (false);
        }
    }
    return (true);
}

void    find_sequence(int index, int n, int m, vector<int> v)
{
    if (index == m)
        print_vector(m, v);
    else
    {
        for (int i = 1; i <= n; )
        {
            v[index] = i++;
            if (!promising(index, v))
            {
                continue;
            }
            find_sequence(index + 1, n, m, v);
        }
    }
}

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> v(m, 0);
    
    find_sequence(0, n, m, v);
}

 

 

 

---

 

#include <iostream>
#include <vector>

using namespace std;

bool    visited[10];
vector  <int> v;

bool    check()
{
    int     before = v[0];
    for (auto& s : v)
    {
        if (s < before)
            return (false);
        before = s;
    }
    return (true);
}

void    select(int n, int k)
{
    if (k == 0)
    {
        if(check())
        {
            for (auto& s : v)
            {
                printf("%d ", s);
            }
            printf("\n");
            return ;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (visited[i])
            continue ;

        visited[i] = true;
        v.push_back(i);

        select(n, k - 1);

        v.pop_back();
        visited[i] = false;
    }
}

int     main()
{
    int n, m;

    scanf("%d %d", &n, &m);
    select(n, m);
    return (0);
}

음.. 엄... (3)은 바로 풀었는데 오름차순 어떻게 하지 고민하다 함수 하나를 추가했다. 

 

---

#include <iostream>
#include <vector>

using namespace std;

bool    visited[10];
vector  <int> v;

void    select(int n, int k, int start)
{
    if (k == 0)
    {
        for (auto& s : v)
        {
            printf("%d ", s);
        }
        printf("\n");
        return ;
    }
    for (int i = start; i <= n; i++)
    {
        if (visited[i])
            continue ;

        visited[i] = true;
        v.push_back(i);

        select(n, k - 1, i + 1);

        v.pop_back();
        visited[i] = false;
    }
}

int     main()
{
    int n, m;

    scanf("%d %d", &n, &m);
    select(n, m, 1);
    return (0);
}

오

 

함수 따로 안 쓰고 풀 수도 있었다. 1부터 n까지 넣는게 아니라 이전 배열 값보다 큰 값 ~ n까지 넣으면 자동으로 오름차순이 된다. 

 

신기방기