[C#] 백준 15652번 문제풀이

문제번호: 15652

문제명: N과 M (4)

문제링크: https://www.acmicpc.net/problem/15652

문제내용과 예제 입/출력은 위 문제 링크에서 확인해 주시기 바랍니다.

 

저번에 풀었던 백트래킹 N과 M문제와 이어지는 4번 문제입니다. 이번 문제에는 같은 숫자여도 가능하고, 내림차순이 아니면 된다라는 조건이 추가되었습니다. 그래서 저는 Recur 매개변수로 들어가는 기존의 start + 1 값을 start로 바꾸어 중복을 허용하였습니다.

다음은 정답코드입니다.

public static void Main()
{
    StreamReader sr = new StreamReader(Console.OpenStandardInput());
    StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

    int[] NM = Array.ConvertAll(sr.ReadLine().Split(), int.Parse);
    int N = NM[0];
    int M = NM[1];

    Stack<int> rs = new Stack<int>();

    Recur(0, 1);

    void Recur(int num, int start)
    {
        if (num == M)
        {
            foreach (int a in rs.Reverse())
            {
                sw.Write(a + " ");
            }
            sw.WriteLine();
            return;
        }

        for (int i = start; i < N + 1; i++) // 1 ~ 4
        {
            rs.Push(i);
            Recur(num + 1, i);
            if (rs.Count > 0)
                rs.Pop();
        }
    }

    sr.Close();
    sw.Close();
}