글 읽기 - C++ 계속 시간초과가 나와요

wldnjs3633 3년 전 0

백트래킹 DFS로 문제 풀이를 했는데요

처음 틀렸을때 시간초과가 나서 두 팀 스코어의 차이만 구하면 되니 멤버를 뽑는 순이 오름차순에 중복이 안되는 걸로 구했는데요

그래도 시간초과로 나오더라고요...

이걸 어떻게 해결해야 하는지 모르겠는데 부탁드릴게요ㅠㅠㅠㅠㅠㅠ

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

vector<int> start;
vector<int> link;
int arr[20][20]={0,};
int gap=__INT_MAX__;
bool check[20]={false,};            //해당 선수를 뽑았는지 확인
int sizenum;

void calteam(){
    int startscore=0,linkscore=0;
    int ggap;
    for(int i=0;i<sizenum/2;i++)
        for(int j=0;j<sizenum/2;j++){
            //해당 팀 선수들의 능력치 점수를 합산
            startscore+=arr[start[i]][start[j]]+arr[start[j]][start[i]];    
            linkscore+=arr[link[i]][link[j]]+arr[link[j]][link[i]];
        }
    ggap=abs(startscore-linkscore);
    //그 차이가 적으면 저장
    if(gap>ggap) gap=ggap;
    return ;
}

//백트래킹 조건 : 중복되는 선수는 하면 안됨//오름차순으로 뽑기(중복금지를 위한 방법)
//start팀 조건(벡터 구분으로 조건을 나눔)
bool startpromising(int num){
    if(start.empty()) return true;        //벡터가 비어있을 경우는 제외
    else return start.back()<num+1&&!check[num];
}
//link팀 조건(벡터 구분으로 조건을 나눔)
bool linkpromising(int num){
    if(link.empty()) return true;        //벡터가 비어있을 경우는 제외
    //link팀 멤버는 start멤버 보다 뒷번호여야 되고 link팀의 마지막 멤버보다 뒷번호여야함
    else return start.back()<num+1&&link.back()<num+1&&!check[num];
}

void backtracking(int num){
    if(num==sizenum/2) calteam();      //sizenum/2 만큼 뽑기 진행
    else{
        for(int i=0;i<sizenum;i++){
            //start 팀에 위 선수가 이미 뽑혔는지 확인
            if(startpromising(i)) {
                start.push_back(i);
                check[i]=true;
            }
            else continue;

            //링크 팀에 위 선수가 이미 뽑혔는지 확인
            for(int j=0;j<sizenum;j++){
                if(linkpromising(j)) {
                    link.push_back(j);
                    check[j]=true;
                }
                else continue;
                
                //다음 뽑기 진행
                backtracking(num+1);

                //끝났으니 pop
                link.pop_back();
                check[j]=false;
            }
            
            //끝났으니 pop
            start.pop_back();
            check[i]=false;
        }
    }
}

int main(void){   
    ios_base::sync_with_stdio(false);       
    cin.tie(nullptr), cout.tie(nullptr);            //cin과 cout의 묶음을 풀어주는(untie) 역할

    cin>>sizenum;

    // 데이터 입력
    for(int i=0;i<sizenum;i++)
        for(int j=0;j<sizenum;j++) cin>>arr[i][j];
    
    backtracking(0);

    cout<<gap/2;
    return 0;
}

아마 backtracking 함수 안에 있는 2중 for문 때문인 것 같습니다. 사실 매번 백트래킹 함수를 호출할 때마다 O(N^2)으로 스타트팀과 링크팀을 뽑기보다는, O(N)으로 스타트팀을 먼저 뽑아낸 후에, 스타트팀에서 뽑은 인원이 sizenum / 2이 됐을 때(즉 base case일때) calteam 함수에서 O(N)에 링크팀을 뽑아내는 것이 더 빠를 거에요. 스타트팀이 아닌 사람은 모두 링크팀일테니 걸러내기도 더 수월하실 겁니다.

kokodak 3년 전 0

음, 뭔가 O(N^2)으로 나타내니 좀 표현이 이상한 것 같아서 수정하자면, 2중 for문을 한 개의 for문으로 줄여서 한 팀의 인원만 확정시킨 뒤에, base case에 들어갈 때만 나머지 팀의 인원을 확정시키면 된다는 뜻이었습니다.

wldnjs3633 3년 전 0

감사합니다 해결됬어요^^

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

문제

문제

출처

ICPC

C++ 계속 시간초과가 나와요

wldnjs3633 3년 전 0

kokodak 3년 전 1

kokodak 3년 전 0

wldnjs3633 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말