[백준] 15654번 : N과 M (5) [C/C++]

#문제

15654번: N과 M (5)

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

15654번: N과 M (5)

 

---

#접근방법

n개의 자연수가 주어졌을 때 오름차순이며 중복되는 수열을 여러 번 출력하면 안된다.

 

입력값으로 랜덤의 숫자가 주어지므로 sort함수로 오름차순 정렬을 한 뒤

 

중복을 체크하기위해 check 배열을 만들고, 모든 수열을 출력하기 위해 백트래킹 기법을 사용하면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <algorithm>
using namespace std;

int n,m;

int arr[10];
int num[10];
int check[10];

void seq(int len){
    if(len==m){
        for(int i=0;i<m;i++)
            printf("%d ",arr[i]);
        printf("\n");
        return;
    }

    for(int i=0;i<n;i++){
        if(check[i]==0){
            arr[len] = num[i];
            check[i] = 1;
            seq(len+1);
            check[i] = 0;
        }
    }

    return;
}

int main(){
    scanf("%d %d",&n,&m);

    for(int i=0;i<n;i++)
        scanf("%d",&num[i]);

    sort(num,num+n);

    seq(0);

    return 0;
}

 

num배열에 n개의 숫자를 받고 sort함수로 오름차순 정렬을 해준다.

 

이 때, sort함수를 사용하려면 #include <algorithm>헤더파일과 using namespace std;를 작성해줘야 한다.

 

seq(0)을 호출하게 되면, 오름차순으로 정렬된 num배열에서 차례대로 arr배열에 들어가게 된다.

 

check배열을 만들어서 어떤 값이 들어가 있으면 그 수의 index에 해당하는 곳에 1과 0으로 유무를 판단하여 중복값을 체크해주었다.

 

만들어진 수열의 길이가 M이 되면 출력하게 만들어서 답을 구하였다.

---

#성능

---

#정리

모든 조합을 구하는 문제는 백트래킹 기법을 사용해야 한다는 것,

 

백트래킹 기법을 사용하기 위해 자기자신을 호출하는 재귀함수를 쓴다는 것,

 

sort함수를 사용할 때 algorithm해더파일과 using namespace std;를 적어줘야 한다는 것,

 

check배열을 만들어서 중복값을 체크해야 한다는 것을 알고 있으면 풀 수 있는 문제였다.