[BOJ / C++] 15649번 - N과 M (1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

 

문제

 

 

풀이

백트래킹으로 푼다.

int arr[ ] : 수열을 담을 배열

bool isused[ ] : 특정 수가 쓰였는지를 나타내는 배열

func(k)는 현재 k개 까지의 수를 택한 상황에서 arr[k]를 정하는 함수이다.

base condition을 설정한다(m개를 모두 택했을 때)

재귀함수를 이용한다(base condition으로 수렴) => 1부터 n까지의 수에 대해 아직 i가 사용되지 않았으면, arr[k]를 i로 정하고 isused[i]를 true로 설정한다. 이후 func(k+1)을 호출하고 나중에 func(k)로 돌아왔을 때 isused[i]를 false로 바꾼다.(왜냐하면 arr[k] = i인 경우에 대해 모든 케이스를 확인했으므로 다시 i를 사용가능한 상태로 놓아야하기 때문이다)

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int arr[9];
bool isused[9];

void func(int k)
{
  //base condition
  if (k==m)
  {
    for (int i=0; i<m; i++)
    {
      cout << arr[i] << ' ';
    }
    cout << '\n';
    return;
  }
  for (int i=1; i<=n; i++)
  {
    if (!isused[i])
    {
      arr[k] = i;
      isused[i] = true;
      func(k+1);
      isused[i] = false;
    }
  }
}

int main()
 {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  cin >> n >> m;
  func(0);
 }

 

 

결과