백준 15650, 15652 (DFS)

15650번: N과 M (2)

 

15652번: N과 M (4)

과정

• 처음 보자마자 다중 for문이 생각났다.
• 다중 for문이면 대부분 DFS로 풀 수 있던걸 생각해서 DFS로 접근
• 처음에는 감이 안잡혔는데, 다음 그림을 그리게 된다.

 

1~6까지 수를 기준으로 3개의 숫자를 가진 수열을 만든다고 쳤을 때,시작은 무조건1부터, DFS의 재귀를 사용해서 1 → 2 로 이동, 같은 방법으로 2 → 3으로 이동한다.3까지 갔으면, 3개의 숫자를 가지므로 3부터 마지막 숫자인6까지 반복후 출력하고,다시 첫 시작인 1로 돌아가서 2부터 같은 방식으로 반복한다.

 

코드

#15650

#include <iostream>

#include <vector>

using namespace std;

int N = 0;  // 1~N

int M = 0;  // 1줄당 M개의 숫자를 가진 수열

// number[i] = j : number자체가 하나의 수열이 된다.(재활용할거임)

// 하나의 수열에서 i번째 숫자가 j가 된다.

vector<int> number; // 숫자를 넣어둘 벡터

void DFS(int start, int count)

{

    // 원하는 숫자만큼 수열을 채웠으면 출력

    if(count == M)

    {

        for (int i = 0; i < M; i++)

            cout << number[i] << " ";

        cout << "\n";

    }

    // 원하는 숫자만큼 수열을 채울때까지 수열 채우기

    else

    {

        for (int i = start; i < N+1; i++)

        {

            number[count] = i;

            DFS(i+1, count+1);

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N >> M;

    number.resize(N+1, 0);

    DFS(1,0);

}

 

#15652

#include <iostream>

#include <vector>

using namespace std;

int N = 0;  // 1~N

int M = 0;  // 1줄당 M개의 숫자를 가진 수열

// number[i] = j : number자체가 하나의 수열이 된다.(재활용할거임)

// 하나의 수열에서 i번째 숫자가 j가 된다.

vector<int> number; // 숫자를 넣어둘 벡터

void DFS(int start, int count)

{

    // 원하는 숫자만큼 수열을 채웠으면 출력

    if(count == M)

    {

        for (int i = 0; i < M; i++)

            cout << number[i] << " ";

        cout << "\n";

    }

    // 원하는 숫자만큼 수열을 채울때까지 수열 채우기

    else

    {

        for (int i = start; i < N+1; i++)

        {

            number[count] = i;

            // 15650과 다르게 시작을 본인 번호부터 시작해야 하기때문에

            // i+1이 아닌 i를 넣어준다.

            DFS(i, count+1);

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N >> M;

    number.resize(N+1, 0);

    DFS(1,0);

}