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

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

• 응시 사이트 : BOJ

• 문제 : 15650.N과 M(2)

• 사용언어 : C#

• 난이도 :

• 풀이시간 : 10m Under

• 유형 : 백트래킹

문제

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

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

• 고른 수열은 오름차순이어야 한다.

입력

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

출력

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

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

예제 입력 1 복사

3 1

예제 출력 1 복사

1
2
3

예제 입력 2 복사

4 2

예제 출력 2 복사

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

예제 입력 3 복사

4 4

예제 출력 3 복사

1 2 3 4

문제 풀이 접근

이 문제는 순열 문제중에서도 가장 쉽게 접할 수 있는 형태다.
현재 진입한 Pos 값이상만큼만 확인해서 Cnt 처리만 해주면 쉽게 풀린다.

작성 코드 (C#)

using System;
using System.Collections;
using System.Collections.Generic;
using System.Xml.Linq;
using static CodingTestProj.Program;

///*
// * Difficulty : Easy
// * URL : https://www.acmicpc.net/problem/15650
//  * Time : 10m Under
// */

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

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

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

        public int _curPos;

        public bool[] _isVisit;

        public void solve()
        {
            string[] _input = Console.ReadLine().Split(' ');
            _n = int.Parse(_input[0]);
            _m = int.Parse(_input[1]);

            _isVisit = new bool[_max];
            _arr = new int[_max];
            _per = new int[_max];

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

            dfs(0,0);
        }

        public void dfs(int _cnt, int pos)
        {
            if (_cnt >= _m)
            {
                for(int i = 0; i < _cnt; ++i)
                {
                    Console.Write(_per[i]);

                    if (i != _cnt-1)
                        Console.Write(" ");
                }

                Console.WriteLine();
            }
            else
            {

                for (int i = pos; i < _n; ++i)
                {
                    if (_isVisit[i] == false)
                    {
                        _isVisit[i] = true;
                        _per[_cnt] = _arr[i];
                        dfs(_cnt + 1, i +1);
                        _isVisit[i] = false;
                    }
                }
            }
        }
    }
}

코드 결과