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

백트래킹의 응용 2번째 문제다.

Bruteforce를 이렇게 푸는 것이 효율적이다.

 

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

 

---

 

먼저 풀이부터 보자

# 맞는 풀이

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int N, M; // N까지의 수, M개 선택

vector<int> vec;

int check[9]; // 사용체크

//현재 숫자보다 큰 것이 들어가게끔 해야함.
void func(int cnt, int cur) {
    if (cnt == M) {
        for (auto c : vec) {
            cout << c << " ";
        }
        cout << "\n";

        return;
    }

    for (int i = 1; i <= N; i++) {
        if (cur > i)continue; // 현재숫자보다 작은 경우는 조사할 필요 없음
        if (check[i] == 1) continue; // 쓰인 숫자는 조사하지 않음.
        check[i] = 1;
        vec.push_back(i);

        ///구현
        func(cnt+1, i); // 현재 들어간 숫자는 i임

        //상태 복원
        vec.pop_back();
        check[i] = 0;
    }
}


int main() {
    cin >> N >> M;
    //1-N 까지의 수를 중복없이 M개 뽑아서 출력(오름차순)
    func(0, 1);
    

}

 

처음에는 cnt만 집어넣어서 넣다보니

수열이 중복되어서 나왔다.

다시 말해서

1,2와 2,1이 같이 나온 것이다.

오름차순으로 뽑으려면

2에서 1을 뽑는 경우는 안되며 당연히 자기 자신을 뽑지도 않고 자기보다 큰 숫자만 뽑아야 한다.

 

때문에 

 

일반적인 백트래킹에서

int(cur > i) continue;

를 집어넣어서 

 

완성했다

 물론 cur는 전 결과에서 받아와야하기 때문에 func의 파라미터로 쓰였다.

 

조금씩 감이 오는데

아직 멀었다.