백준, BOJ, 15657번 C++ [CPP]

이 문제도

백트래킹으로 어렵지 않은 문제다.

다만 출력 조건에 맞게끔 선택하려면

선택 과정에서 필터가 있어야 한다.

 

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

---

 

#맞은 풀이

#include<iostream>
#include<vector> //N개의 수를 담을 벡터
#include<algorithm> //오름차순 정렬

using namespace std;


int N,M;

vector<int> vec; // N개의 수를 담을 벡터
vector<int> ans; // 수열을 넣을 벡터

void func(int cnt){
    if(cnt == M){
        //M개 골랐다면 출력
        for(int a : ans){
            cout << a << " ";
        }
        
        cout << '\n';
        return;
    }
    
    for(int i = 0; i<N; i++){
        //선택 조건: 비내림차순, 같은 수 여러번가능
        if(!ans.empty()){ // 비어있지 않다면 선택할 때 가장 뒤에있는 것보다 크거나 같은 걸 선택
            if(ans.back()<=vec[i]){
                ans.push_back(vec[i]);
            }else{
                continue; // 그렇지 않다면 다음 숫자로.
            }
        }else{
            ans.push_back(vec[i]);
        }
        
        //구현
        func(cnt+1);
    
        //복원
        ans.pop_back();
        
        
    }

}

int main(){
    cin >> N >> M;
    
    // N개의 수를 받음
    for(int i = 0; i<N; i++){
        int a;
        cin >> a;
        vec.push_back(a);
    }
    
    sort(vec.begin(), vec.end());
    
    
    func(0);
    
}

 

여기선 필터가 이미 선택한 숫자보다 작은 값이 들어와선 안된다는 것이다.

즉, 중복된 값을 선택하게 될 때 조심해야한다.

하지만 나는 맨 뒤에 것을 조사함으로써 맨 앞부터 맨 뒤까지 반내림차순임의 정당성을 끌어내었다.

 

하지만 입력이 주어진대로 선택을 시작하면 분명 선택은 제대로 했지만

출력 순서가 제대로 나오지 않는다.

 

결과를 모아서 다시 정렬할 생각했지만 당연히

처음부터 오름차순대로 정렬하면 조건에 맞게끔 나와서 그렇게 했다.