PS/백트래킹[Backtracking]

백준 N과 M (6) ~ (12) 복습

SeungbeomKim 2023. 2. 11. 02:02

오늘도 N과 M 시리즈를 복습 차원에서 다시 풀어보았습니다. 유형마다 조금씩 차이도 있고, 함수 구현하는데 있어 도움이 많이 될 것 같아서 다시 풀어보았습니다. 

6 ~ 12번 까지 문제 설명 드리겠습니다. 

6번 : N개의 자연수 중에서 M개를 고른 수열, 고른 수열은 오름차순이어야 한다.

7번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다.(사전 순으로 증가하는 순서로 출력)

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

9번 : N개의 자연수 중에서 M개를 고른 수열(중복 수열 제거, set 사용 or vector에서 중복원소 제거)

10번 : N개의 자연수 중에서 M개를 고른 수열, 고른 수열은 비내림차순이어야 한다.

11번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다.

12번 : N개의 자연수 중에서 M개를 고른 수열, 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다.

<코드>

6번

#include <iostream>
#include <algorithm>

using namespace std;
int n, m;
bool check[9];
int num[9];
int result[9];
void print(int idx)
{
    if (idx == m)
    {
        for (int i = 1; i < m; i++)
        {
            if (result[i] < result[i - 1])
                return; 
            // 수열이 오름차순 정렬되어야 되기 때문에, 이전 인덱스 값이 더 크면 수열이 될 수 없다.
        }
        for (int i = 0; i < m; i++)
        {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (check[i])
            continue;
        check[i] = true;
        result[idx] = num[i];
        print(idx + 1);
        check[i] = false;
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    sort(num, num + n);
    print(0);
}

7번 

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int num[8];
int result[8];

void print(int idx)
{
    if (idx == m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i = 0; i < n; i++)
    {
        result[idx] = num[i];
        print(idx + 1);
        // 같은 수 중복 사용 가능하기에 boolean타입 check변수 불필요
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    sort(num, num + n);

    print(0);
}

8번

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int num[9];
int result[9];
bool check[9];

void print(int idx, int start)
{
    if (idx == m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i = start; i < n; i++)
    {
        result[idx] = num[i];
        print(idx + 1, i);
        //비내림차순 조건을 충족시키기 위해 매개변수 start를 두어 다음 인덱스에 이전 인덱스의 값이상이 들어오도록 설정
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    sort(num, num + n);

    print(0, 0);
}

9번

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>

using namespace std;

int num[9];
int result[9];
bool check[9];
set<vector<int>> s;
vector<int> v;
vector<int>::iterator elem;
int n, m;

void print(int idx)
{
    if (idx == m)
    {
        for (int i = 0; i < m; i++)
        {
            v.push_back(result[i]);
        }
        s.insert(v);
        // 중복 원소 제거하기 위해 set헤더 이용
        v.clear();
        // 벡터에 새로운 값을 대입해야 하기 때문에 clear해주고 새롭게 시작
        return;
    }
    for (int i = 0; i < n; i++)
    {
        if (!check[i])
        {
            check[i] = true;
            result[idx] = num[i];
            print(idx + 1);
            check[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    sort(num, num + n);
    print(0);

    for (auto v : s)
    {
        for (auto elem : v)
        {
            cout << elem << ' ';
        }
        cout << '\n';
    }
}

10번

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>

using namespace std;

int num[9];
int result[9];
bool check[9];
set<vector<int>> s;
vector<int> v;
vector<int>::iterator elem;
int n, m;

void print(int idx, int start)
{
    if (idx == m)
    {
        for (int i = 0; i < m; i++)
        {
            v.push_back(result[i]);
        }
        s.insert(v);
        v.clear();
        return;
    }
    for (int i = start; i < n; i++)
    {
        if (!check[i])
        {
            check[i] = true;
            result[idx] = num[i];
            print(idx + 1, i);
            check[i] = false;
        }
        // 비내림차순 조건을 충족
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    sort(num, num + n);
    print(0, 0);

    for (auto v : s)
    {
        for (auto elem : v)
        {
            cout << elem << ' ';
        }
        cout << '\n';
    }
}

11번

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>

using namespace std;

int num[9];
int result[9];
bool check[9];
set<vector<int>> s;
vector<int> v;
vector<int>::iterator elem;
int n, m;

void print(int idx)
{
    if (idx == m)
    {
        for (int i = 0; i < m; i++)
        {
            v.push_back(result[i]);
        }
        s.insert(v);
        v.clear();
        return;
    }
    for (int i = 0; i < n; i++)
    {
        result[idx] = num[i];
        print(idx + 1);
        //중복원소 허용하기에 check변수 불필요
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> num[i];
    }
    sort(num, num + n);
    print(0);

    for (auto v : s)
    {
        for (auto elem : v)
        {
            cout << elem << ' ';
        }
        cout << '\n';
    }
}

12번

#include <iostream>
#include <set>
#include <algorithm>
#include <vector>

using namespace std;

int num[9];
int result[9];
bool check[9];
set<vector<int>>s;
vector<int>v;
vector<int>::iterator elem;
int n, m;

void print(int idx, int start)
{
    if(idx == m)
    {
        for(int i=0;i<m;i++)
        {
            v.push_back(result[i]);
        }
        s.insert(v);
        v.clear();
        return;
    }
    int last = 0;
    for(int i=start;i<n;i++) 
    {
        if(last != num[i])
        {
            check[i] = true;
            result[idx] = num[i];
            last = num[i];
            print(idx+1, i);
            check[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>num[i];
    }
    sort(num,num+n);
    print(0, 0);
    
    for(auto v : s)
    {
        for(auto elem : v) {
            cout<<elem<<' ';
        }
        cout<<'\n';    
    }

}

질문 및 피드백 환영입니다. 저는 N과 M 시리즈에서 매개변수는 순열의 순서를 나타내는 idx와 비내림차순 조건을 충족시키기 위해 start를 두어 풀었습니다. 9번 문제부터는 set헤더를 이용해서 중복된 순열을 제거해주었습니다. 

 

저작자표시 비영리 변경금지

'PS > 백트래킹[Backtracking]' 카테고리의 다른 글

백준 N과 M (1) ~ (5) 복습  (2) 2023.02.10
백준 14500 테트로미노(c++)  (0) 2023.01.28
백준 6603 로또(c++)  (0) 2023.01.28
백트래킹(backtracking)  (0) 2022.08.10

'PS/백트래킹[Backtracking]'의 다른글

  • 현재글백준 N과 M (6) ~ (12) 복습

관련글

댓글

티스토리툴바