[백준/c++] 15650번 N과 M (2)

15650번 문제 링크

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

N과 M(1) 이 순열을 사용해서 푸는 문제였다면 N과 M(2) 는 조합을 사용해서 푸는 문제다.

조합 관련해서 포스팅은 👉 [알고리즘] 조합 (Combination) 여기를 참고

푸는 방법은 재귀를 사용하는 방법과 백트래킹을 사용하는 방법 총 두가지가 있는데 두 가지 모두로 풀어봤다.

소스코드

① 백 트래킹 사용

#include <iostream>
#include <stdio.h>

using namespace std;

int visited[9];
int n, m;

void combination(int index, int count) { // count개의 수를 이용해 조합을 만듬
    if (count == m) {
        for (int i = 1; i <= n; i++) {
            if (visited[i] == true) // 조합과 순열의 차이 (조합은 중복 제거)
                cout << i << " ";
        }
        cout << endl;
        return;
    }
    
    for (int i = index; i <= n; i++) {
        // 이미 방문한 곳이라면 건너뛴다.
        if (visited[i] == true) continue;
            
        visited[i] = true; // 방문 표시를 남긴다.
        combination(i, count + 1);
        visited[i] = false; // 체크 취소 (다른 자식 노드를 체크하기 위해)
    }
}
int main() {
    cin >> n >> m;
    
    combination(1, 0);

}

② 재귀 사용

#include <iostream>
#include <stdio.h>

using namespace std;

int n;
int m;

/**
 arr : 대상 배열
 print_arr : 출력 배열
 r : 남은 뽑아야할 갯수
 index : print_arr 의 인덱스
 depth : 대상 배열에서 뽑을 원소를 결정하는 인덱스
 */
void combination(int arr[], int print_arr[], int r, int index, int depth) {
    if(r == 0) {                // 뽑아야할 갯수가 모두 없어진 경우에는 print_arr 에 들어있는 값 모두 출력
        for(int i=0;i< m;i++){
            cout << print_arr[i] << " ";
        }
        cout << endl;
    } else if (n == depth) { // 뽑을 원소 인덱스가 대상 배열의 마지막까지 온 경우 return
        return;
    } else {
        print_arr[index] = arr[depth];
        combination(arr, print_arr, r-1, index+1, depth+1); // n-1Cr-1: 특정 원소를 뽑은 경우
        
        combination(arr, print_arr, r, index, depth+1);     // n-1Cr: 특정 원소를 뽑지 않은 경우
    }
}


int main() {
    
    cin >> n >> m;
    
    int print_arr[m];
    int arr[n];
    
    for(int i=0;i<n;i++) {
        arr[i] = i+1;
    }
        
    combination(arr, print_arr, m, 0, 0);
    
}

정답