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

문제번호: 15651

문제명: N과 M (3)

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

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

 

오늘은 엔과앰 문제 시리즈를 이어서 풀었습니다. 이번 문제는 저번 N과 M (1) 문제에서 걸었었던 조건중 하나인 중복불가를 허용한 문제였습니다. 그래서 중복을 거르기 위해 사용했던 chk bool배열을 삭제해주었습니다. 이로 인해 1 1, 2 2와 같은 중복 수열 출력이 가능해졌습니다.

다음은 정답코드입니다.

 

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>();
    bool[] chk = new bool[N + 1];

    Recur(0);

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

        for (int i = 1; i < N + 1; i++)
        {
            //if (chk[i] == false)
            {
                //chk[i] = true;
                rs.Push(i);
                Recur(num + 1);
                //chk[i] = false;
                if (rs.Count > 0)
                    rs.Pop();
            }
        }
    }

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