15649번

15649번 - N 과 M (1)

개인적으로 이런 간단한 기본 문제가 있으면 좋겠다고 생각했는데 문제가 생겼다.

문제를 풀다보면 응용해서 써야하는 자주 접하는 기본 문제인 것 같다. 그래서 재귀를 이용해서 풀었고 , 비트연산을 이용해보기도 하였다.

<정답 코드 - 단순 재귀>

#include<stdio.h>
 
int n, m;
int num[9];
bool used[9];
void go(int cnt)
{
    if (cnt == m)
    {
        for (int i = 0; i < cnt; i++) {
            printf("%d ", num[i]);
        }
 
        printf("\n");
        return;
    }
 
    for (int i = 1; i <= n; i++) {
        if (!used[i])
        {
            used[i] = true;
            num[cnt] = i;
            go(cnt + 1);
            used[i] = false;
        }
    }
 
 
}
int main()
{
    scanf("%d %d", &n, &m);
 
    go(0);
 
    return 0;
}

<정답 코드 - 단순 재귀 & 비트 마스크>

#include<stdio.h>
 
int n, m;
int num[9];
 
void go(int k,int cnt)
{
 
    if (cnt == m)
    {
        for (int i = 0; i < cnt; i++)
            printf("%d ", num[i]);
 
        printf("\n");
        return;
    }
 
    for (int i = 1; i <= n; i++) {
        if ((k & 1 << i) == 0)
        {
            k |= 1 << i;
            num[cnt] = i;
            go(k, cnt + 1);
            k &= ~(1 << i);
        }
    }
 
}
int main()
{
    scanf("%d %d", &n, &m);
 
    go(0,0);
 
    return 0;
}