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

문제 링크 - https://www.acmicpc.net/problem/15654

[문제]

[풀이]

• 이전 시리즈와 다른점은 수열을 구성하는 값들이 (사용자)입력으로 주어진다.
• input이라는 배열을 선언하여, 0번째 인덱스부터 순서대로 값을 입력받고 sort를 이용해 정렬하였다.
• 이전 문제들과 마찬가지로, check[input[i]]을 통해 input[i]에 해당하는 값을 중복체크 해주었다.

[배열 정렬]

#include<algorithm> 선언
sort(arr,arr+n) 
- 첫번째 인자 : 배열의 시작지점 (=배열의 포인터)
- 두번재 인자 : 배열 끝나는지점+1 (=arr[배열의 포인터]+배열의 크기)

[헤맸던 점]

• 처음엔 check[], arr[], input[] 배열을 동일하게 크기가 10인 배열로 선언해주었었다.
• 문제의 조건을 살펴보면 입력으로 주어지는 수들은 10000보다 같거나 작은 자연수이다.
• check 배열은 입력으로 들어온 수가 func함수에서 수열을 만드는데 사용했는지 체크하는 배열이므로,check[]의 인덱스는 0~10000이 되어야 한다.
• check[10001]로 수정함으로써 해결 할 수 있었다.

[코드]

//15654번 : N과 M(5)
#include <iostream>
#include <algorithm>
using namespace std;

bool check[10001];
int arr[10];
int input[10];

void func(int index, int n, int m){
    if(index>m){
        for(int i=1; i<=m; i++){
            cout<<arr[i] <<" ";
        }
        cout<<"\n";
        return;
    }

    for(int i=0; i<n;i++){
     
        if(check[input[i]])
        continue;

        check[input[i]]=true;
        arr[index]=input[i];
        func(index+1,n,m);
        check[input[i]]=false;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n,m;
    cin>>n>>m;
    for(int i=0; i<n; i++){
        int x;
        cin>>x;
        input[i]=x;
    }
    sort(input,input+n);
    // func(index,n,m);

    func(1,n,m);
}

참고 사이트
https://twpower.github.io/71-use-sort-and-stable_sort-in-cpp