[백준] 15654_N과 M (5) C++

17 Jun 2023 in Study on Coding Test

백트래킹 기본을 배워보는 문제

정답제출코드

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

using namespace std;

int N, M;
vector<int> arr;
vector<int> arrOutput;

bool Search(int a)
{
    for (size_t i = 0; i < arrOutput.size(); ++i)
    {
        if (arrOutput[i] == a)
            return true;
    }
    return false;
}

void backtrack(int count)
{
    if (count == M)
    {
        for (size_t i = 0; i < arrOutput.size(); ++i)
            cout << arrOutput[i] << ' ';
        cout << '\n';

        return;
    }

    for (size_t i = 0; i < arr.size(); ++i)
    {
        if (!Search(arr[i]))
        {
            arrOutput.push_back(arr[i]);
            backtrack(count+1);
            arrOutput.pop_back();
        }
    }
}


int main()
{
    cin >> N >> M;

    for (int i = 0 ; i < N; ++i)
    {
        int _input;
        cin >> _input;

        arr.push_back(_input);
    }

    sort(arr.begin(), arr.end());

    backtrack(0);

    return 0;
}

오랜만에 휴식을 하고 싶지만 스트릭은 채워야 하기 때문에 풀어본 실버문제.

백트래킹을 통해서 조건을 만족하는 모든 경우의 수를 구하는 문제이다.

이 때, 중복된 숫자가 들어가면 안되므로 값이 arr에 없을 경우에만 넣도록 구현하였다.

bool Search(int a)
{
    for (size_t i = 0; i < arrOutput.size(); ++i)
    {
        if (arrOutput[i] == a)
            return true;
    }
    return false;
}

...

for (size_t i = 0; i < arr.size(); ++i)
{
    if (!Search(arr[i]))
    {
        arrOutput.push_back(arr[i]);
        backtrack(count+1);
        arrOutput.pop_back();
    }
}

그리고 arrOutput에 몇 개를 넣었는지를 backtrack 함수의 입력인자로 받으면서

M과 값이 일치할 경우 그 때 arrOutput에 들어간 값들을 순서대로 출력해준다.