[C++] 백준 15649번 : N과 M (1)

15649번: N과 M (1)

---

문제

---

풀이

순서와 관련된 문제이다.

 

만약, M = 3, N = 5 일 경우 숫자는 중복 없이 골라야 하므로

첫 번째에 올 수 있는 숫자는 총 5가지,

두 번째에 올 수 있는 숫자는 첫 번째에 나온 숫자를 제외한 4가지,

마지막 세 번째에 올 수 있는 숫자는 첫 번째와 두 번째에 나온 숫자를 제외한 3가지가 된다.

 

이를 써보면

1 2 3

1 2 4

1 2 5

1 3 2

1 3 4

1 3 5

1 4 2

1 4 2 ···

처럼 진행된다.

 

결과를 저장할 배열 a와 bool 타입의 배열 check를 만들어

check[i] 의 값이 true이면 사용한 숫자이고, false이면 사용하지 않은 숫자를 뜻하므로 false일 때만 배열 a에 값을 저장하면 원하는 결과를 저장할 수 있다.

또한, 재귀함수를 사용하여 매개변수로 index값을 1씩 증가시키고 index의 값과 m의 값이 같을 때 출력을 하면 정답을 구할 수 있다.

---

문제점

재귀함수로 진행하려 하다 보니 이해하는데 어려움을 겪었는데 손으로 직접 써보면서 하니 생각보다 쉽게 이해를 할 수 있었다.

---

코드

#include <iostream>
using namespace std;

int a[8];
bool check[8];

void go(int index, int n, int m)
{
    if (index == m)
    {
        for (int i = 0; i < m; ++i)
        {
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (check[i])
        {
            continue;
        }
        check[i] = true;
        a[index] = i;
        go(index + 1, n, m);
        check[i] = false;
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    go(0, n, m);

}

---

결과

---

 

pyo7410/Study