[백준] 15657번 : N과 M (8) [C/C++]

#문제

15657번: N과 M (8)

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

15657번: N과 M (8)

 

---

#접근방법

n개의 자연수가 주어졌을 때 오름차순이며 같은 수를 여러 번 골라도 된다.

 

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

 

모든 수열을 출력하기 위해 백트래킹 기법을 사용하면 된다.

반응형

---

#풀이

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

int n,m;

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

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

    for(int i=x;i<n;i++){
        arr[len] = num[i];
        seq(i,len+1);
    }

    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,0);

    return 0;
}

 

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

 

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

 

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

 

이 때, 반복문에서 x ~ i 사이의 값만 arr배열에 넣어서 비내림차순이 되도록 설계하였다.

 

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

---

#성능

---

#정리

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

 

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

 

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

 

비내림차순을 만들기 위해 seq(i,len+1)을 호출하고 반복문에서 x ~ i까지의 숫자만 arr배열에 넣도록 설계하면 풀 수 있는 문제였다.