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

문제(Problem)

 

풀이(Solution)

이 문제는 조합의 개수를 이용하는 문제이며 재귀함수와 간단한 로직으로 풀이가 가능합니다. 문제의 핵심 포인트를 말씀드리자면, 1~N까지의 자연수를 고르는데 중복이 불가능하다는 점입니다. 

각 숫자들을 딱 한 번씩만 사용할 수 있도록 visited 배열로 사용 여부를 체크하여 중복을 피해줍니다.(visited가 fasle이면 -> 사용 / visited 가 true이면 -> 사용 불가)

func 함수와 print 함수를 사용하였으며 각각 조합을 뽑는 함수(func 함수), depth가 m이 되었을 때 출력하는 함수(print 함수)로 구성됩니다.

 

func의 재귀 호출이 M번 이루어지면(즉, visited의 true의 개수가 m이 되면) print 함수를 통해 계속해서 결과를 출력해줍니다.

 

 

코드(Code)

#include<iostream>
using namespace std;
int n, m;
int visited[9];
int arr[9];

void print() {
  for(int i=0; i<m; i++) 
    cout << arr[i] << ' ';
  cout << '\n';
}

void func(int depth) {
  if(depth==m) {
    print();
    return;
  }

  for(int i=1; i<=n; i++) {
    if(visited[i]) continue;
    visited[i]=1;
    arr[depth]=i;
    func(depth+1);
    visited[i]=0;
  }
}

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