글 읽기 - 백트래킹에 어려움을 겪고 있습니다. 도와주시면 감사드리겠습니다.

dudgh9661 3년 전 1

25, 27 라인을 지우면 왜 맞고 지우지 않으면 왜 틀리는지, 이해가 가지 않습니다. 오름차순으로 정렬했기 때문에, SUM > S인 지점에서 더 나아가봤자 SUM은 더 커지지 않기 때문에 가지치기가 가능한것 아닌가요?

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

using namespace std;

int N, S = 0, ans = 0;
bool isFirst = true;

vector<int> vec;

void init() {
    cin >> N >> S;
    int a;
    for(int i = 0; i < N; i++) {
        cin >> a;
        vec.push_back(a);
    }
}

void DFS(int sum, int idx) {
    //종료조

    //이미 정렬된 상태이므로, 더 나아가봐야 수가 더 커지기 때문에 pruning 해준다.
    if( sum > S  ) {
        return;
    }

    //같은 경우 답을 ++해주고 종료시킨다. 왜? 더 나아가봐야 수가 커지기 때문!
    if( sum == S && !isFirst) {
        ans++;
//        return;
    }
    //진입 조건
    isFirst = false;
    if( idx == N ) return;
    for(int i = idx; i < vec.size(); i++) {
        DFS(sum + vec[i], i + 1); //선택
    }
}

int main() {
    init();
    sort(vec.begin(), vec.end(), less<>());
    DFS(0,0);
    cout << ans << endl;
    return 0;
}

dudgh9661 3년 전 0

이유를 알았습니다.

반례로, S가 -5이고 원소들이 .. , .. , -4, -1 일 때 예외가 발생합니다.

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

문제

문제

출처

ICPC

백트래킹에 어려움을 겪고 있습니다. 도와주시면 감사드리겠습니다.

dudgh9661 3년 전 1

dudgh9661 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말