코딩테스트 준비 - N과 M(4)

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : BOJ

• 문제 : 15652.N과 M(4)

• 사용언어 : C#

• 난이도 : Easy ~ Middle

• 풀이시간 : 21m

• 유형 : 백트래킹 , DFS

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열

• 같은 수를 여러 번 골라도 된다.

• 고른 수열은 비내림차순이어야 한다.

  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

예제 입력 3 복사

3 3

예제 출력 3 복사

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

문제 풀이 접근

이 문제에서는 요구사항이, 이전 수보다 이상인 들을 이용하여 순열을 구성하는것이다.
가능과 불가능 케이스를 나누자면,

가능

• 1 1 1

• 1 1 2

• 1 2 3

불가능

• 1 2 1

• 1 3 2

• 1 4 1

즉 이전 수 보다 작으면 안된다는 얘기다.
이 문제는 단순하게 Cnt, Pos 값으로 해결할 방법을 찾아보았으나, 이전 수를 넣어주는 파라미터를 추가하여, 0부터 순회하지만, 이전수인 Prev 보다 작을 경우 Continue로 순회할 수 있도록 작성해주었더니 문제를 풀 수 있었다.

플로우에 대한 케이스는 이렇게 된다.

1 2 3 4 가 있을때, 4 개 중 2개를 뽑는다.
_per 에는 1 x 가 들어가고, 1 2 , 1 3 , 1 4 가 모두 순회한 후에 2 x 를 구하는 번째에서 prev 의 값인 arr[i] 값을 파라미터로 넣으면 1이 들어간다.
그렇게되면 2 x 에서 x 는 arr의 i 가 0 부터 순회를 하게되는데 arr[0] == 1 이기때문에 continue로 통과하게 된다.
그 이후 i 가 1로 증가하여 arr[1] 의 값을 참조하면 2 이기 때문에 2 x 에서 2 2 를 뽑아낼 수 있게된다.

이렇게 값이 증가하여 문제에서 요구하는 순열을 구성할 수 있게되어, 문제를 해결할 수 있다.

작성 코드 (C#)

using System;
using System.Collections.Generic;
using System.IO.Pipes;
using System.Linq;
using System.Runtime.InteropServices;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System.Threading.Tasks;

///*
// * Difficulty : Easy
// * URL : https://www.acmicpc.net/problem/15652
//  * Time : 21m
// */

namespace Test
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Solution solution = new Solution();
            solution.solve();
        }
    }


    public class Solution
    {
        public const int max = 9;
        public int _n;
        public int _m;

        public int[] _arr;
        public int[] _per;

        public StringBuilder _sb;

        public void solve()
        {
            _sb = new StringBuilder();
            string[] _in  = Console.ReadLine().Split(' ');

            _n = int.Parse(_in[0].ToString());
            _m = int.Parse(_in[1].ToString());

            _arr = new int[max];

            for(int i = 0; i < max; ++i)
                _arr[i] = i + 1;

            _per = new int[max];

            dfs(0, 0,0);

            Console.Write(_sb.ToString());
        }
        public void dfs(int cnt, int pos, int prev)
        {
            if(cnt  >= _m)
            {
                for(int i = 0; i < cnt; ++i)
                {
                    _sb.Append(_per[i]);

                    if(i != cnt -1 )
                        _sb.Append(" ");
                }

                _sb.AppendLine();
            }
            else
            {
                for(int i = 0; i < _n; ++i)
                {
                    if (_arr[i] < prev) continue;

                    _per[pos] = _arr[i];
                    dfs(cnt+1, pos + 1, _arr[i]);
                }
            }
        }
    }
}

코드 결과