[알고리즘 문제 풀기] N과 M (2)(15650)

1. 문제 풀이 아이디어

• 재귀함수를 사용하여 문제를 해결할 수 있다.

2. 나의 정답 코드

StreamReader reader = new StreamReader(Console.OpenStandardInput());
StreamWriter writer = new StreamWriter(Console.OpenStandardOutput());
string[] split = reader.ReadLine().Split();
int n = int.Parse(split[0]);
int m = int.Parse(split[1]);
int[] result = new int[m];
int prev = -1;
int count = 0;
solve();
writer.Close();
reader.Close();
void solve()
{
    if (count == m)
    {
        for (int i = 0; i < m; i++)
        {
            writer.Write($"{result[i] + 1} ");        
        }
        writer.WriteLine(); 
        return;
    }    
    for (int i = prev + 1; i < n; i++)    
    {        
        if (i <= prev) continue; 
        result[count++] = i;
        prev = i;        
        solve();        
        prev = i;        
        count--;    
    }
}

3. 정리

• prev를 -1, count를 0으로 초기화하고 재귀 함수 solve를 호출한다.

• solve에서 count가 m과 같으면 저장된 result 배열을 출력한다.

• 반복문에서 prev + 1부터 n 미만까지 숫자를 순회한다.

• result 배열의 현재 위치에 숫자를 저장하고, count를 증가시킨다.

• 현재 숫자를 prev로 설정한 뒤 재귀 호출을 통해 다음 숫자를 선택한다.

• 재귀 호출이 끝나면 prev와 count를 이전 상태로 복구하여 백트래킹한다.

• 반복문이 종료되면 모든 가능한 조합이 출력된다.