알고리즘 질문입니다!

안녕하세요 현재 아래의 문제를 풀던중에 계산을해서 0이 성립하도록 무작위 대입으로 알아내도록 코드를 작성 하였습니다. 이때문에 14마리 이상부터 결과값을 출력하는데 많은 시간이 걸려서 단시간에 결과를 구할수있는 코드를 작성해보고 싶습니다. 이와 관련된 알고리즘이나 방법을 조언받고자 질문글 작성합니다. (소스코드는 문제 밑에 올려 놓겠습니다.)

[문제]
농부 John은 소들의 저녁식사 줄 세우는 새로운 방법을 개발하였다. 
N(1~15)마리의 소들을 순서대로 세워놓은 후, 각 소들 사이에 +, - , . 셋 중 1가지가 써져 있는 냅킨을 배치해서 최종 결과가 0이 되게 하는 것이다. 
점(.)이 써져 있는 냅킨을 통해 더 큰 수를 만들 수 있게 된다. 점(.) 냅킨은 ‘공백'이라고 생각하면 된다

1 – 2 . 3 – 4 . 5 + 6 . 7
이와 같은 배치는 1-23-45+67을 나타낸다. 결과는 0이다. 
즉, 10.11은 1011로 해석하면 된다.

[입력]
소들의 수 N이 입력된다

[출력]
처음 20줄에 대해 가능한 20가지 답을 출력하는데, 사전 순으로 앞선 것을 출력한다.
순서는 +가 가장 앞서고 –와 .이 순서대로 뒤따른다.
답이 20개 미만이면 가능한 답을 각 숫자와 문자 사이에 공백을 두고 출력한다
마지막 줄에는 가능한 답의 총 가지 수를 출력한다.

[예제 입력]
7
[예제출력]
1 + 2 – 3 + 4 – 5 – 6 + 7
1 + 2 – 3 – 4 + 5 + 6 - 7
1 – 2 + 3 + 4 – 5 + 6 - 7
1 – 2 – 3 – 4 – 5 + 6 + 7
1 – 2 . 3 + 4 + 5 + 6 + 7
1 – 2 . 3 – 4 . 5 + 6 . 7
6
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define End 0
#define Dot 1
#define Plus 3
#define Minus 2

struct _cow{
    int cow_num;
    int type;
    int val;
    struct _cow *next;
} typedef cow;

struct _calc_result{
    cow *result;
    struct _calc_result *next;
} typedef calc_result;

char tmp[0x100];

cow *create_cows(int n){
    cow *result= malloc(sizeof(cow));
    cow *tmp = result;

    for(int i=0; i<n; i++){
        tmp->cow_num = i+1;
        tmp->val = i+1;
        tmp->type = Dot;
        if( i+1 == n)
            break;
        tmp->next = malloc(sizeof(cow));
        tmp = tmp->next;
    }
    tmp->type=End;
    return result;
}

void delete_cow_list(cow *list){
    if(list->type != End)
        delete_cow_list(list->next);
    free(list);
}

cow *parse_dot(cow *list){
    cow *tmp_list = list;
    cow *parse_result = malloc(sizeof(cow));
    cow *result = parse_result;
    while(1){
    if(tmp_list->type == Dot){
        memset(tmp, 0, 0x100);
        sprintf(tmp, "%d%d", tmp_list->val, tmp_list->next->val);
        tmp_list->next->val = atoi(tmp);
    }else{
       parse_result->val = tmp_list->val;
       parse_result->type = tmp_list->type;
       parse_result->cow_num = tmp_list->cow_num;

       if(tmp_list->type == End)
            return result;
       parse_result->next = malloc(sizeof(cow));
       parse_result = parse_result->next;
    }
    tmp_list = tmp_list->next;
    }
}

int calc(cow *list){

    cow *tmp;
    int lval, rval;

    tmp = parse_dot(list);
    lval = tmp->val;

    while(1){
    switch(tmp->type){
        case Dot:
            tmp = tmp->next;
            break;
        case End:
            delete_cow_list(tmp);
            return lval;
        case Plus:
            rval = tmp->next->val;
            lval = lval + rval;
            tmp = tmp->next;
            break;
        case Minus:
            rval = tmp->next->val;
            lval = lval - rval;
            tmp = tmp->next;
            break;
        default:
            printf("calc error!\n");
            exit(-1);
            break;
    }
    }

}

void print_cow(cow *list){
    switch(list->type){
        case End:
            printf("%d\n", list->cow_num);
            return;
        case Dot:
            printf("%d . ", list->cow_num);
            return print_cow(list->next);
        case Plus:
            printf("%d + ", list->cow_num);
            return print_cow(list->next);
        case Minus:
            printf("%d - ", list->cow_num);
            return print_cow(list->next);
        default:
            printf("print error!\n");
            exit(-1);
    }
}

void print_result(calc_result *list){
    int count = 0;
    for(calc_result *p = list; p->result && count < 20; p = p->next){
        print_cow(p->result);
        count++;
    }
}

void clear_val(cow *list){

    cow *tmp = list;

    for(int i = 0; ; i++){
        tmp->val= i+1;
        if(tmp->type == End)
            break;
        tmp = tmp->next;
    }
}

void copy_cows(cow *a, cow *b){
    a->cow_num = b->cow_num;
    a->val = b->val;
    a->type = b->type;
    if(b->type == End)
        return;
    a->next = malloc(sizeof(cow));
    copy_cows(a->next, b->next);
}

int cows_compare(cow *a, cow *b){
    if(a->type == End)
        return 0;
    else if(a->type == b->type)
        return cows_compare(a->next, b->next);
    else if(a->type > b->type)
        return -1;
    else
        return 1;
}

void sort(calc_result *list){
    calc_result *head=list, *prev, *tmp;
    cow *c_tmp;

    //1->2->3->4
    //2->1->3->4
    //2->3->1->4
    //3->2->1->4
    //3->2->4->1
    while(head->result != NULL){
    for(calc_result *p = head->next; p->result; p = p->next){
            if(cows_compare(head->result, p->result) == 1){
                c_tmp = p->result;
                p->result = head->result;
                head->result = c_tmp;

                p = head;
                //printf("xchg\n");
            }
    }
        head = head->next;
    }
}

int find_cows(calc_result *list, cow *src)
{
    if(list->result == NULL)
        return 0;
    else if(cows_compare(list->result, src) == 0)
        return 1;
    return find_cows(list->next, src);
}

void brute_force(cow *list, int n){
    cow *tmp=list;
    cow *a = list;
    calc_result *result = malloc(sizeof(calc_result));
    calc_result *p = result;
    int count = 0;
    int test_count = 0;

    while(1){
        clear_val(list);
        if(calc(list) == 0){
            if(!find_cows(result, list)){
            cow *tmp2 = list;
            cow *tmp3 = malloc(sizeof(cow));
            copy_cows(tmp3, tmp2);
            p->result = tmp3;
            p->next = malloc(sizeof(calc_result));
            p = p->next;
            count++;
            sort(result);
            }
        }
        if(tmp->type == End)
            break;
        if((tmp->type+1) > 3){
            tmp->type=1;
            tmp = tmp->next;
        }else{
            tmp->type += 1;
            tmp = list;
        }
    } 
    sort(result);
    print_result(result);
    printf("%d\n", count);
}

int main(){
    int n, result, count;
    cow *cows;

    scanf("%d", &n);
    cows = create_cows(n);
    brute_force(cows, n);
}
  • 이거 소한테 연산자 주는 문제 이거 대체 어느 대학교 문제인데 이렇게 자주 올라오나 ㅋㅋㅋㅋㅋㅋ 광자 2018.6.11 19:59
  • 정답 출력은 되는데 너무 오래걸려서 어떻게 단축 시킬 수 있을지 조언 부탁드립니다 ㅠㅠㅠ yeonnic 2018.6.11 20:06
  • 몇초나 걸려요? 그리고 어디 문젭니까? 광자 2018.6.11 20:28

1답변

  • 좋아요

    3

    싫어요
    채택취소하기
    1. 멀티쓰레드. 이 문제는 멀티쓰레드 프로그래밍 하면 CPU 쓰레드 숫자만큼 시간 감소할겁니다.
    2. 브렌치 앤 컷. 전체 숫자가 얼마인지는 모르겠지만, 예를 들어서 8까지 있는데, 1~6까지 모두 다 +를 준 상태라면, 21이니까, 7,8이 모두 - 여도 절대로 도달 못합니다. 굳이 다 -인지 아닌지 넣어볼 필요가 없다는거죠. 이런 식으로 미리 싹수가 노랗다는 것을 판별하는 함수를 작성해서 그 루트를 탐색하지 않는 식으로.
    • 앗 2번 방법으로 해보겠습니다 감사합니다! yeonnic 2018.6.12 09:29

ᕕ( ᐛ )ᕗ
로그인이 필요합니다

작성한 답변에 다른 개발자들이 댓글을 작성하거나 댓글에 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.