[백준] 15666번 : N과 M (12) [C/C++]

#문제

15666번: N과 M (12)

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

15666번: N과 M (12)

 

---

#접근방법

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

 

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

반응형

---

#풀이

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

    int last = 0;

    for(int i=x;i<n;i++){
        if(num[i]!=last){
            arr[len] = num[i];
            last = arr[len];
            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부터 초기값을 만들어 주었으며 seq(i,len+1)을 호출함으로써 같은 수를 여러번 고를 수 있도록 하였다.

 

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

 

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

 

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

 

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

---

#성능

---

#정리

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

 

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

 

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

 

고른 수열이 비내림차순이 되도록 반복문의 초기값을 x로 설정한 것,

 

같은 수를 여러번 고를 수 있도록 seq(i,len+1)에서 i를 호출한 것,

 

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