[백준] 15652번 N과 M (4) - C/C++

백준 15652 문제(Problem)

백준 15652 문제

 

풀이(Solution)

이 문제는 조합과 재귀함수를 이용하여 풀 수 있는 문제이다. 문제의 포인트는 같은 수를 여러번 골라도 되고, 수열은 사전 순으로 증가하는 순서로 출력해야한다는 점이다. 이는 재귀적으로 함수를 호출 할 때 인자값으로 pos를 보냄으로써 해결할 수 있다.

 

재귀적으로 호출할 함수는 func 함수이다. depth가 M이 되었을 때 즉, 조합이 M개 이루어졌을 때 해당 조합의 원소를 출력한다. 

 

func 함수의 인자값을 통해 받은 pos부터 반복문을 시작하여, 출력할 a배열을 업데이트 해주어 서로 다른 조합을 생성하였다.

 

이 문제는 재귀 함수를 통해 조합을 만들 줄 알기만 하면 어렵지 않은 문제이다.

 

코드(Code)

#include<iostream>
using namespace std;
int N, M, a[9];

void func(int pos, int depth) {
  if(M==depth) {
    for(int i=0; i<M; i++)
      cout << a[i] << ' ';
    cout << '\n';
    return;
  }

  for(int i=pos; i<=N; i++) {
    a[depth]=i;
    func(i, depth+1);
  }
}

int main() {
  cin >> N >> M;
  func(1, 0);
}