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

백트래킹 문제다.

풀다 보니 감이 조금씩 온다.

 

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

 

---

 

조금씩 감이 오긴 온다.

 

#맞는 풀이

#include<iostream>
#include<vector>

using namespace std;

int N, M;
vector<int> vec;

void func(int cnt) {
    if (cnt == M) {
        //선택 종료 시
        for (int n : vec) {
            cout << n << " ";
        }
        cout << "\n";
        //함수 종료.
        return;
    }

    //1~N까지 선택 (중복가능) 하지만 선택된 숫자보다 작은 숫자는 나올 수 없음
    for (int i = 1; i <= N; i++) {
        //선택
        //비어있다면 그냥 넣음
        if (vec.empty()) {
            vec.push_back(i);
            //비어있지 않다면 현재 들어간 마지막 원소보다 크거나 같은 원소만 선택 가능
        }
        else {
            if (vec.back() <= i) {
                vec.push_back(i);
            }
            //아니면 다음 선택으로 넘어감.
            else {
                continue;
            }
            
        }
        //구현
        func(cnt + 1);

        //복원
        vec.pop_back();
    }
}
int main() {
    cin >> N >> M;
    func(0);
}

 

 

백트래킹은 선택, 구현, 복원이 있다.

선택을 했다면 그 다음 방법을 구현해야하고

구현이 끝난 뒤에는 그 선택을 되돌려서 다른 선택에 쓰일 수 있도록 한다.

 

간단하다.

하지만 이제 구현이나 선택에 있어서 조건을 주어서 어렵게 만들 뿐이다.

 

아니면 백트래킹 문제인 것을 헷갈리게 해서 인지를 못하게 만들거나..ㅎ