백준/단계별

백준 15652 C#) N과 M (4)

alpacadabra 2023. 3. 8. 18:04

이전에 풀었던 N과 M (1)과 거의 유사한 문제다.

 

class Program
{
    static StreamWriter sw = new(new BufferedStream(Console.OpenStandardOutput()));

    static int n, m;
    static int[] result;

    static void DFS(int depth, int start)
    {
        if (depth == m)
        {
            sw.WriteLine(string.Join(' ', result));
            return;
        }

        for (int i = start; i <= n; i++)
        {
            result[depth] = i;
            DFS(depth + 1, i);
        }
    }

    static void Main()
    {
        string[] nm = Console.ReadLine().Split();

        (n, m) = (int.Parse(nm[0]), int.Parse(nm[1]));
        result = new int[m];

        DFS(0, 1);
        sw.Close();
    }
}

 

풀이는 (1)과 거의 동일하다.

다만,

- 같은 수를 여러 번 골라도 되므로 visited 배열은 필요하지 않다.

- 고른 수열이 비내림차순이어야 하므로 직전에 선택한 노드(숫자)를 인자로 전달하여 for문에 활용하였다.

 

 

백준 15649 C#) N과 M (1)

백트래킹 및 DFS의 기본을 익힐 수 있는 문제. 시리즈가 굉장히 많으므로 틈틈이 하나씩 풀면 좋다. class Program { static StreamWriter sw = new(new BufferedStream(Console.OpenStandardOutput())); static int n, m; static int[]

sete3683.tistory.com

 

(1)을 안 풀어봤다면 위의 글을 참고하자.