백준 15649. N과 M (1)

15649. N과 M (1)

• 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 모두 구하는 문제이다.
• 최근에 역량 테스트에서는 거의 모든 문제에 N개중 M개를 고르는 것이 기본으로 들어가 있고 고른 것을 바탕으로 시뮬레이션을 하기 때문에 N개중 M개를 고르는 문제는 기본기로서 상당히 중요하다고 생각한다.
• 기본적이지만 선택하는 것이 꼬이면 끝까지 꼬일 수 있다고 생각한다.(개인적으로 경험이 있어서...)

풀이 과정

1. 선택한것은 중복으로 선택하지 않기 위해 visit배열을 따로 만들었다.
2. 선택하지 않았다면 선택후 visit를 true로 바꿔주고 go함수를 재귀 호출 하였다.
3. count개만큼 선택했다면 저장한것들을 출력해주고 반환하였다.
4. 반환하면서 visit도 false로 바뀌고 다시 선택할 수 있게 된다.

소스 코드

#include<iostream>

using namespace std;

int n, m;
bool visit[10];
int arr[10];

void go(int count)
{
    // m개만큼 다 뽑았을 때
    if (count == m)
    {
        for (int i = 0; i < m; i++)
        {
            printf("%d ", arr[i] + 1);
        }
        printf("\n");
    }

    for (int i = 0; i < n; i++)
    {
        // 중복을 피하기 위해 visit배열 체크
        if (!visit[i])
        {
            visit[i] = true;
            arr[count] = i;
            go(count + 1);
            visit[i] = false;
        }
    }
}

int main()
{
    cin >> n >> m;
    go(0);
    return 0;
}

전체 소스 코드