글 읽기 - 14889번 시간초과

kanght1219 3년 전 0

시간초과가 일어나는 이유는 뭘까요?

#include<iostream>
using namespace std;
int ex[20][20];//경험치
bool used1[20];//1팀 사용
bool used2[20];//2팀 사용
int n;//사람 수
long long int mini = 100000;//최솟값
int sumi = 0;//1팀 합
int sumj = 0;//2팀 합
int cnti = 0;//1팀 명수
int cntj = 0;//2팀 명수
int abs(int x){//절댓값
    if (x<0) return -x;
    return x;
}
void search(int x){
    if (cnti > n/2 || cntj > n/2) return;//사람 수 이상하면 리턴
    else if (x == n){//최솟값 찾으면 대입 뒤 리턴
        if (abs(sumi-sumj) < mini) mini = abs(sumi-sumj);
        return;
    }
    for (int i=0;i<n;i++){
        if (used1[i] || used2[i]) continue;//어디든 사용됐음 리턴
        used1[i] = 1;//1팀 선수 추가
        for (int j=0;j<n;j++){
            if (used1[j] && i!=j) sumi += (ex[i][j] + ex[j][i]);//경험치 더하기
        }
        cnti++;//1팀 선수 명수 추가
        search(x+1);//재귀
        for (int j=0;j<n;j++){
          if (used1[j] && i!=j) sumi -= (ex[i][j] + ex[j][i]);//다시 삭제
        }
        cnti--;//다시 선수 삭제
        used1[i] = 0;//다시 선수 삭제

        used2[i] = 1;//이젠 2팀에 추가
        for (int j=0;j<n;j++){
            if (used2[j] && i!=j) sumj += (ex[i][j] + ex[j][i]);//2팀 경험치 추가
        }
        cntj++;//선수 1명 증가
        search(x+1);//재귀
        for (int j=0;j<n;j++){
          if (used2[j] && i!=j) sumj -= (ex[i][j] + ex[j][i]);//경험치 삭제
        }
        cntj--;//1명 삭제
        used2[i] = 0;//선수 삭제
    }  
}
int main(){
    cin.tie(NULL); ios::sync_with_stdio(false);
    cin >> n;//선수 수 입력
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            cin >> ex[i][j];//경험치 입력
        }
    }
    search(0);//함수 돌리기
    cout << mini;//최솟값 출력
    return 0;
}

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

문제

문제

출처

ICPC

14889번 시간초과

kanght1219 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말