알고리즘 질문입니다!

조회수 1053회

안녕하세요 현재 아래의 문제를 풀던중에 계산을해서 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
  • 정답 출력은 되는데 너무 오래걸려서 어떻게 단축 시킬 수 있을지 조언 부탁드립니다 ㅠㅠㅠ 알 수 없는 사용자 2018.6.11 20:06
  • 몇초나 걸려요? 그리고 어디 문젭니까? 광자 2018.6.11 20:28

1 답변

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

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)