히든퀘스트 브루트포스 질문

작성한 질문수 28

1

안녕하세요 명운님 ㅎㅎ

명운님의 로직은 타당합니다.

다만, 시간초과가 나는 것은요.

기저사례 부분을 보았을 때 함수호출을 조금은 더 많이 하게 되어서 시간초과가 나타나는 것 같습니다.

이렇게 조금만 바꾸시면 됩니다.

#include <iostream>
using namespace std; 
int N, M, a[104], ret;
void go(int idx, int num, int _ret){
    if(idx >= N) return;  
    //cout << idx << " : " << num << " : " << _ret << "\n";
    if(num == 3){
        if(_ret > M) return; 
        ret = max(ret, _ret);
        return; 
    }
    go(idx + 1, num + 1, _ret + a[idx + 1]);
    go(idx + 1, num, _ret);
    return;  
} 
int main(){
    cin >> N >> M; 
    for(int i = 0; i < N; i++) cin >> a[i];
    go(-1, 0, 0);
    cout << ret << "\n"; 
    return 0;
} 

코드리뷰를 좀 드리면요

void go(int cnt, int sum, int chk) {
    if (ret == M) return;

이 문제는 M을 넘지 않아야 합니다. 즉, 넘으면 종료시키는 부분이 필요한데 이렇게 M과 같을 때 return을 하게 되는 경우의 수가 몇이나 될까요? 많은 경우의 수를 걸러내지 못합니다.

    if (cnt == N) {
        if (sum <= M && chk == 3) ret = max(ret, sum);
        return;
    }

이렇게 되면 무조건 완탐을 했을 경우 중첩 if문이 작동됩니다.

가지치기를 못하는 코드입니다.

이 문제는 chk == 3일 때 체킹을 해야 합니다.

왜그러냐면 chk == 3일 때 체킹을 '먼저' 하게 되면 N까지 다 안돌아도 해당 부분을 확인하고 함수호출을 더이상 안할 수 있거든요.

나머지 부분은 괜찮습니다. ㅎㅎ

또 질문 있으시면 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다.

감사합니다.