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

문제번호: 15657

문제명: N과 M (8)

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

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

 

오늘도 N과M 시리즈 문제를 풀었습니다. 오늘은 8번째 문제였습니다. 추가된 문제 조건은 '비내림차순'이어야 한다라는 조건이었습니다. 비 내림차순이란 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 합니다. 따라서 두번째 인자값 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);
    List<int> Numbers = Array.ConvertAll(sr.ReadLine().Split(), int.Parse).ToList();
    Numbers.Sort();
    int N = NM[0]; // 3
    int M = NM[1]; // 1

    Stack<int> rs = new Stack<int>();
    bool[] chk = new bool[N + 1]; // 4

    Recur(0, 1);

    void Recur(int num, int start)
    {
        if (num == M)
        {
            //Console.WriteLine(rs.ToString());
            foreach (int a in rs.Reverse())
            {
                sw.Write(a + " ");
            }
            sw.WriteLine();
            return;
        }
        for (int i = start; i < N + 1; i++)
        {
            int number = Numbers[i - 1];
            //if (chk[i] == false)
            {
                //chk[i] = true;
                rs.Push(number);
                Recur(num + 1, i);
                //chk[i] = false;
                if (rs.Count > 0)
                    rs.Pop();
            }
        }
    }

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