[백준] 5568번 카드 놓기

문제

https://www.acmicpc.net/problem/5568

고민

상근이는 카드 4 ~ 10장을 바닥에 나란히 놓음

각 카드는 1 ~ 99이하 정수가 적힘

 

상근이는 이 카드 중 2 ~ 4장을 선택, 가로로 나란히 정수를 만듦

상근이가 만들 수 있는 정수는 몇가지? ⇒ 조합 O

 

동일한 카드지만 순서가 다르면 다른 숫자가 됨 ⇒ 순열 X

코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BackTracking
{
    internal class 카드_놓기
    {
        static int n, k;
        static int[] cards;
        static HashSet<string> numbers = new HashSet<string>();
        static int[] number;
        static bool[] visited;
        static int answer = 0;
        static void Main(string[] args)
        {
            n = int.Parse(Console.ReadLine()); // 카드 수
            k = int.Parse(Console.ReadLine()); // 선택 수

            // 만들어질 숫자가 들어가는 배열 초기화
            number = new int[n];

            // 방문 정보 초기화
            visited = new bool[n];

            // 카드 배열 초기화
            cards = new int[n];

            for (int i = 0; i < cards.Length; i++)
            {
                cards[i] = int.Parse(Console.ReadLine());
            }

            BT(0, 0);

            Console.WriteLine(numbers.Count);
        }

        static void BT(int depth, int count)
        {
            // k만큼 선택되면 count 증가
            if (count >= k) 
            {
                // 중복 방지를 위해 완성된 숫자를 hash set에 삽입
                string s = null;
                foreach(int i in number)
                {
                    s += i.ToString();
                }
                numbers.Add(s);

                return;
            }
            
            for (int i = 0;i < cards.Length;i++)
            {
                if (visited[i] == false)
                {
                    visited[i] = true;
                    number[depth] = cards[i];
                    BT(depth + 1, count + 1);
                    visited[i] = false;
                }
                    
            }

        }
    }
}

백트래킹 할 때 for문 사용을 지양하는 편인데(왜냐하면 예전에 시간초과 났던 적이 있음) 숫자가 적어서 상관 없으려나,, 는 마음에 쉬운 길로 가봤다.

 

 for문을 사용 vs 하지 않음에 대해서 재귀적으로 코드가 어떻게 호출되는지 정리 할 필요가 있어보인다.