글 읽기 - [c++] 백트래킹이 뭔지 모르고 풀어봤는데..

lja3723 1년 전 0

백트래킹이 뭔지 모르고 그저 재귀를 써야 풀리겠다는 생각만으로 몇시간 고민한후 작성해서 맞았습니다!! 띄운 제 코드입니다.

그런데 다른 분들 코드를 봤는데 거의 dfs? 라는 식별자를 사용하면서 코드 길이가 두배 가까이 짧게 풀던데 제 방식이랑 무슨 차이가 있을까요? ㅠㅠ

엄청 어렵게 풀었는데 뭔가 허무하네요..

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

bool next_picks(int N, int M, vector<int>& picks, int picks_range) {
    if (!(0 < picks_range && picks_range <= M)) return false;
    else if (next_picks(N, M, picks, picks_range - 1)) return true;
    else {
        int cur_idx = M - picks_range;
        int prev_pick = picks[cur_idx];
        set<int> no_picks;
        for (int i = 1; i <= N; i++) no_picks.insert(i);
        for (int i = 0; i < cur_idx; i++) no_picks.erase(picks[i]);

        auto next_pick = find_if(
            no_picks.begin(), no_picks.end(),
            [prev_pick](int elem) { return elem > prev_pick; }
        );
        if (next_pick != no_picks.end()) {
            picks[cur_idx] = *next_pick;
            no_picks.insert(prev_pick);
            no_picks.erase(*next_pick);
            auto it = no_picks.begin();
            for (int i = cur_idx + 1, j = 0; i < M; i++, j++) {
                picks[i] = *(it++);
            }
            return true;
        }
        else return false;
    }
}

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int N, M; cin >> N >> M;
    vector<int> picks(M);
    for (int i = 0; i < M; i++) picks[i] = i + 1;

    do {
        for_each(picks.begin(), picks.end(), [](int e) { cout << e << " "; });
        cout << "\n";
    } while (next_picks(N, M, picks, M));

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[c++] 백트래킹이 뭔지 모르고 풀어봤는데..

lja3723 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말