코딩 테스트 준비! (백준)/DFS

[DFS] 백준 15652번 N과 M (4,5,6) (C++)

lee-soo 2025. 4. 8. 13:35

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

 

해당 문제를 풀기전 1,2,3을 풀고오길 바란다

https://lee-soo.tistory.com/17

 

[DFS] 백준 15649번 N과 M (1,2,3) (C++)

https://www.acmicpc.net/problem/15649 이 문제를 풀면서 나에게도 큰 시련이 찾아왔다. 도저히 못풀겠다 사실 글쓴이는 아직 코테 초보수준이라 해본게 브루트 포스랑, dp 랑.. 자료구조 뭐 이런것들인

lee-soo.tistory.com

 

사실 앞선 문제를 풀었다면, 이제부턴 너무너무너무너무너무너무 쉽다

정답률이 보이는가? 허허이..

 

이번엔 비 내림차순으로 고르라는데 중복을 포함한 오름차순을 말하는거네..

#include <iostream>
#include <vector>

using namespace std;
void task(int n, int m, int depth);
vector<int> result;
int main()
{
    int n, m;
    cin >> n >> m;
    task(n, m, 0);
}
void task(int n, int m, int depth)
{
    if (m == depth)
    {
        for (int i = 0; i < m; i++)
        {
            cout << result[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (result.empty() || i >= result.back())
        {
            result.push_back(i);
            task(n, m, depth + 1);
            result.pop_back();
        }
    }
}
단순하다.
앞선 식에서
i > = result.back()을 해주면 알아서 오름차순으로 된다

머여이건

 

이번엔 내가 따로  지정한 숫자들을 통해서 수열을 만들어야 되잖아?

 

그냥 arr을 매개변수로 전해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
bool visited[10];
using namespace std;
void task(int n, int m, int depth, int *arr);
vector<int> result;
int main()
{
    int n, m;

    cin >> n >> m;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    task(n, m, 0, arr);
}
void task(int n, int m, int depth, int *arr)
{
    if (m == depth)
    {
        for (int i = 0; i < m; i++)
        {
            cout << result[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            result.push_back(arr[i]);
            task(n, m, depth + 1, arr);
            result.pop_back();
            visited[i] = false;
           
        }
    }
}
주의해야 될것이, arr을 새로 넣고, push_back에 arr을 넣어주어야한다!
 
또한 사전순으로 출력되어야 하니까 sort 함수를 사용하여 미리 정렬 후 함수 호출을 하였따

 

이제 앞선 문제들하고 비슷한 류의 문제만 나온다.

 

오름차순으로 출력해야된다고?

그럼 내가 앞선 1,2,3에서 사용한 방법만 사용하면 된다

 

#include <iostream>
#include <vector>
#include <algorithm>
bool visited[10];
using namespace std;
void task(int n, int m, int depth, int *arr);
vector<int> result;
int main()
{
    int n, m;

    cin >> n >> m;
    int arr[n];
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);
    task(n, m, 0, arr);
}
void task(int n, int m, int depth, int *arr)
{
    if (m == depth)
    {
        for (int i = 0; i < m; i++)
        {
            cout << result[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 0; i < n; i++)
    {
        if (!visited[i] && (result.empty() || arr[i] >= result.back()))
        {
            visited[i] = true;
            result.push_back(arr[i]);
            task(n, m, depth + 1, arr);
            result.pop_back();
            visited[i] = false;
        }
    }
}
 

        if (!visited[i] && (result.empty() || arr[i] >= result.back()))
해당 조건문을 사용하여 풀기! 
끝!
 
남은 7 8 9 10 11 12또한 대동소이한 문제들이고 앞선 문제들을 풀었다면 남은 문제또한 무리없이 풀을 수 있을것이라 생각하여 스킵하겠다