[백준] 15663번 : N과 M (9) [C/C++]

#문제

15663번: N과 M (9)

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

15663번: N과 M (9)

 

---

#접근방법

N개의 자연수 중에서 M개를 고른 수열을 출력하면 된다. 단, 중복되는 수열을 여러 번 출력하면 안된다.

 

모든 경우의 수를 구하는 백트래킹 기법을 사용하면서 적절한 조건문을 추가하면 풀 수 있다.

반응형

---

#풀이

#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;
    }

    int last = 0;

    for(int i=0;i<n;i++){
        if(check[i]==0 && num[i]!=last){
            arr[len] = num[i];
            last = arr[len];
            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배열로 중복으로 사용한 num배열의 값들이 있는지 확인하여 중복으로 사용된 값을 배제 시켜준다.

 

그리고 중복되는 수열을 배제시켜주기 위해서 last라는 변수를 만들어 주었다.

 

last변수는 만들어지고 있는 수열에서 마지막 값을 뜻한다.

 

수열의 마지막 값과 새로 추가되는 값이 같을 때, 중복된 수열이 만들어지므로 num[i]!=last라는 조건문을 넣어서 중복되는 수열을 배제시켜주었다.

 

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

---

#성능

---

#정리

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

 

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

 

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

 

중복되는 값을 막기위해 check배열을 사용한다는 것,

 

중복되는 수열을 막기위해 last라는 변수를 만들어주어서 만들어 지고있는 수열의 마지막 값과 새로 추가되는 값이 같을 때를 조건문으로 배제시켜주어 출력을 하면 정답을 구할 수 있는 문제였다.