[C#] 백준 N과 M (1) (백트래킹 재귀함수)

[ 문제 ]

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

 

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

 

[ 코드 ]

1. 내 코드

using System.Text;

StreamReader sr = new StreamReader(Console.OpenStandardInput());
StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
StringBuilder sb = new StringBuilder();

string[] s = sr.ReadLine().Split();
int n = int.Parse(s[0]);
int m = int.Parse(s[1]);

FindValue(n, m, 1, new int[m]);

sw.Write(sb.ToString().TrimEnd());
sw.Flush();
sw.Close();
sr.Close();

void FindValue(int n, int m, int start, int[] arr)
{
    if (m == 0)
    {
        foreach (int num in arr)
        {
            sb.Append($"{num} ");
        }
        sb.AppendLine();
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (!Array.Exists(arr, x => x == i)) 
        {
            int[] newArr = new int[arr.Length];
            Array.Copy(arr, newArr, arr.Length);
            newArr[newArr.Length - m] = i;
            FindValue(n, m - 1, 1, newArr); 
        }
    }
}

 

2. 다른 사람 코드

using System.Text;
using var sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
using var sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
StringBuilder sb = new StringBuilder();
string[] s = sr.ReadLine().Split();
int n = int.Parse(s[0]);
int m = int.Parse(s[1]);
int[]arr = new int[9];
bool[] visited = new bool[9];
BackTracking(0);
sw.WriteLine(sb);
void BackTracking(int cnt)
{
    if (cnt == m)
    {
        for (int i = 0; i < m; i++)
        {
            sb.Append(arr[i]);
            sb.Append(" ");
        }
        sb.Append("\n");
    }
    else
    {
        for (int i = 1; i <= n; i++)
        {
            if (!visited[i])
            {
                visited[i] = true;
                arr[cnt] = i;
                BackTracking(cnt + 1);
                visited[i] = false;
            }
        }
    }
}

 

- 비슷한 것 같지만 다른 사람 코드는 bool 배열을 써서 간단하게 구현했다.

나는 재귀호출할때마다 기존 배열을 복사해서 new배열을 만들었기때문에 조금 메모리가 크다.

 

땡깡부리는 개발자..

너는 예쁘지만 다른 사람은 돈이 많아서 좋았다라고 대답하는 GPT..

백트래킹.. 너 참 어렵다..

 

[ 실행화면 ]

case: 3

 

 

 

 

 

---

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

15649번: N과 M (1)