글 읽기 - 스타트와 링크 c언어 시간초과 질문있습니다

cdt416z 4년 전 1

DFS 함수 내에서 시간을 줄일려고 stack을 도입해봤는데 시간초과가 나네요

방식이 잘못된 부분이 있다면 지적 부탁드립니다

#include <stdio.h>
#include <math.h>

int nCm[21][21] = { 0 };
int map[21][21];
int visit[21] = { 0 };
int result[21] = { 0 };
int min = 1000000;
int N, stack = 0;

int DFS(int num){
    if(min != 0 && stack <= nCm[N][N / 2] / 2){
        if(num == N / 2){
            stack++;
            int a = 0, b = 0, t = 0, p = 0;
            for(int i = 0; i < N; i++){
                if(visit[i] == 1){
                    result[t++] = i;
                }
                else{
                    result[N / 2 + p++] = i;
                }
            }
            for(int i = 0; i < N / 2; i++){
                for(int j = i + 1; j < N / 2; j++){
                    a += map[result[i]][result[j]] + map[result[j]][result[i]];
                }
            }
            for(int i = N / 2; i < N; i++){
                for(int j = i + 1; j < N; j++){
                    b += map[result[i]][result[j]] + map[result[j]][result[i]];
                }
            }
            if(abs(a - b) < min){
                min = abs(a - b);
            }
        }
        else{
            for(int i = 0; i < N; i++){
                if(visit[i] == 0){
                    visit[i]++;
                    DFS(num + 1);
                    visit[i]--;
                }
            }
        }    
    }
}

int main(){
    for(int i = 0; i <= 20; i++){
        nCm[i][0] = 1;
        nCm[i][i] = 1;
    }
    for(int i = 1; i <= 20; i++){
        for(int j = 1; j <= i; j++){
            nCm[i][j] = nCm[i - 1][j - 1] + nCm[i - 1][j];
        }
    }
    scanf("%d", &N);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            scanf("%d", &map[i][j]);
        }
    }
    DFS(0);
    printf("%d", min);
    return 0;
}

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

문제

문제

출처

ICPC

스타트와 링크 c언어 시간초과 질문있습니다

cdt416z 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말