c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q40 하나의 숫자로 만드는 1234

[문제]

1 ~ 9 중 하나의 숫자만을 사용해서 1234를 만들고자 한다.

예를 들어, 1111 + 111 + 11 + 1 = 1234가 된다. (1이 10개 사용됨)

111 * 11 + 11 + 1 + 1 역시 1234가 된다. (1이 9개 사용됨)

가장 적은 개수를 사용하여 1234를 만들 수 있는 식은?

단, 나눗셈의 경우, 몫을 나타내기로 한다.

예를 들어, 222 / 22 = 10, 22222 / 22 = 1010 이다.

그리고 사칙연산의 우선순위를 그대로 따르기로 하며, 괄호는 사용하지 않는다.

22 + 222 * 2 = 22 + 444 = 466 (곱셈을 먼저 하고 나중에 덧셈을 한다.)  

 

[알고리즘]

Q2. 수열의 사칙연산 문제와 비슷한 문제이다.

단, 그때는 숫자의 개수가 4개, 연산자의 개수도 3개였으므로 간단하였으나, 이번에는 최대 9개 숫자를 연산해야 한다.

먼저 계산식을 배열로 표현하기로 한다.

예를 들어, 55 / 555 + 55 * 5 라는 식이 있을 때

숫자 배열은 당연히 [5, 5, 5, 5, 5, 5, 5, 5]가 될테고,

연산자 배열은 [C, /, C, C, +, C, *]이다. (C는 55, 555 처럼 결합이 된 것을 의미한다)

이제 이 배열들을 가지고 결과를 구하는 함수를 만든다.

1단계) 결합 함수

연산자 배열에 C가 있으면 결합을 우선 처리한다. 

2단계) 곱셈, 나눗셈 함수

다음으로 곱셈과 나눗셈이 있으면 연산한다.

3단계) 덧셈, 뺄셈 함수

마지막으로 덧셈과 뺄셈을 연산한다.

아래 그림은 단계적으로 숫자 배열과 연산자 배열이 변하는 것을 보여주는 것이다.

아래는 각각의 함수이다.

연산자 배열의 i번째 인덱스에 있는 연산 처리를 할 때, 

숫자 배열의 i 번째 인덱스 값은 의미 없는 값(GARBAGE)으로 만들고, i + 1번째 인덱스에 연산 결과를 저장한다.

(의미 없는 값으로 여기서는 -1234를 넣었다. 연산 과정에서 -1234가 등장하는 경우, 그 식은 문제에서 구하고자 하는 답이 절대로 될 수 없다.)

그리고 rearrange 함수를 이용해서 의미 없는 값을 제거하고 의미 있는 값만 남긴다.

int combine(int* arr, int* op, int sz) {
    int size = sz;
    for (int i = 0; i < sz; i++) {
        if (op[i] == c) {
            arr[i + 1] += arr[i] * 10;
            arr[i] = GARBAGE, op[i] = GARBAGE;
            size--;
        }
    }
    rearrange(arr, sz);
    rearrange(op, sz - 1);
    return size;
}
int multiply(int* arr, int* op, int sz) {
    int size = sz;
    for (int i = 0; i < sz; i++) {
        if (op[i] == m) {
            arr[i + 1] *= arr[i];
            arr[i] = GARBAGE, op[i] = GARBAGE;
            size--;
        }
        else if (op[i] == d) {
            arr[i + 1] = arr[i] / arr[i + 1];
            arr[i] = GARBAGE, op[i] = GARBAGE;
            size--;
        }
    }
    rearrange(arr, sz);
    rearrange(op, sz - 1);
    return size;
}
int sum(int* arr, int* op, int sz) {
    for (int i = 0; i < sz; i++) {
        if (op[i] == p) {
            arr[i + 1] += arr[i];
            arr[i] = GARBAGE, op[i] = GARBAGE;
        }
        else if (op[i] == s) {
            arr[i + 1] = arr[i] - arr[i + 1];
            arr[i] = GARBAGE, op[i] = GARBAGE;
        }
    }
    rearrange(arr, sz);
    rearrange(op, sz - 1);
    return arr[0];
}

위 3개 함수를 operation이라는 함수에 집어 넣는다.

int operation(int* arr, int* op, int sz) {
    int size = sz;
    int* temp_arr = (int*)malloc(sizeof(int) * sz);
    int* temp_op = (int*)malloc(sizeof(int) * (sz - 1));
    copy_arr(temp_arr, arr, sz);
    copy_arr(temp_op, op, sz - 1);
    size = combine(temp_arr, temp_op, sz);
    size = multiply(temp_arr, temp_op, size);
    int result = sum(temp_arr, temp_op, size);
    free(temp_arr), free(temp_op);
    return result;
}

아래는 실행 결과이다.

 

이 함수를 이용해서 숫자를 5개 사용하는 경우부터 9개 사용하는 경우까지 탐색을 진행한다.

solve 함수 : 연산자의 모든 조합을 탐색하고, 계산 결과가 1234인지 확인하는 함수

 

아래는 전체 코드

#include <stdio.h>
#include <stdlib.h>
#define TARGET 1234
#define GARBAGE -TARGET
enum op { c = 1, m, d, p, s };
void solve(int* arr, int* op, int num, int n, int index, int* state);
int combine(int* arr, int* op, int sz);
int multiply(int* arr, int* op, int sz);
int sum(int* arr, int* op, int sz);
void rearrange(int* arr, int sz);
void copy_arr(int* arr1, int* arr2, int sz);
void print_arr(int* arr, int sz);
void print_result(int n, int* op, int sz, int target);
int main() {
		
    for (int num = 5; num <= 9; num++) {	// 사용하는 숫자 개수
        int* arr = (int*)malloc(sizeof(int) * num);
        int* op = (int*)malloc(sizeof(int) * (num - 1));
        int state = 0;				// 정답을 찾은 후 루프 탈출을 위한 변수
        for (int n = 1; n <= 9; n++) {		// 1 ~ 9 정수
            for (int i = 0; i < num; i++)	// 배열 초기화
                arr[i] = n;
            solve(arr, op, num, n, 0, &state);
        }
        free(arr), free(op);
        if (state == 1)
            break;
    }
}
void solve(int* arr, int* op, int num, int n, int index, int* state) {
    if (index == num - 1) {
        int result = operation(arr, op, num);	
        if (result == TARGET) {
            *state = 1;
            print_result(n, op, num - 1, TARGET);
        }
        return;
    }
    for (int i = c; i <= s; i++) {
        op[index] = i;
        solve(arr, op, num, n, index + 1, state);
    }
}
int operation(int* arr, int* op, int sz) {
    int size = sz;
    int* temp_arr = (int*)malloc(sizeof(int) * sz);
    int* temp_op = (int*)malloc(sizeof(int) * (sz - 1));
    copy_arr(temp_arr, arr, sz);
    copy_arr(temp_op, op, sz - 1);
    size = combine(temp_arr, temp_op, sz);
    size = multiply(temp_arr, temp_op, size);
    int result = sum(temp_arr, temp_op, size);
    free(temp_arr), free(temp_op);
    return result;
}
int combine(int* arr, int* op, int sz) {
    int size = sz;
    for (int i = 0; i < sz; i++) {
        if (op[i] == c) {
            arr[i + 1] += arr[i] * 10;
            arr[i] = GARBAGE, op[i] = GARBAGE;
            size--;
        }
    }
    rearrange(arr, sz);
    rearrange(op, sz - 1);
    return size;
}
int multiply(int* arr, int* op, int sz) {
    int size = sz;
    for (int i = 0; i < sz; i++) {
        if (op[i] == m) {
            arr[i + 1] *= arr[i];
            arr[i] = GARBAGE, op[i] = GARBAGE;
            size--;
        }
        else if (op[i] == d) {
            arr[i + 1] = arr[i] / arr[i + 1];
            arr[i] = GARBAGE, op[i] = GARBAGE;
            size--;
        }
    }
    rearrange(arr, sz);
    rearrange(op, sz - 1);
    return size;
}
int sum(int* arr, int* op, int sz) {
    for (int i = 0; i < sz; i++) {
        if (op[i] == p) {
            arr[i + 1] += arr[i];
            arr[i] = GARBAGE, op[i] = GARBAGE;
        }
        else if (op[i] == s) {
            arr[i + 1] = arr[i] - arr[i + 1];
            arr[i] = GARBAGE, op[i] = GARBAGE;
        }
    }
    rearrange(arr, sz);
    rearrange(op, sz - 1);
    return arr[0];
}
void rearrange(int* arr, int sz) {
    for (int i = 0; i < sz - 1; i++) {
        if (arr[i] == GARBAGE) {
            for (int j = i + 1; j < sz; j++) {
                if (arr[j] != GARBAGE) {
                    arr[i] = arr[j];
                    arr[j] = GARBAGE;
                    break;
                }
            }
        }
    }
}
void print_arr(int* arr, int sz) {
    for (int i = 0; i < sz; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
void copy_arr(int* arr1, int* arr2, int sz) {
    for (int i = 0; i < sz; i++)
        arr1[i] = arr2[i];
}
void print_result(int n, int* op, int sz, int target) {
    for (int i = 0; i < sz; i++) {
        printf("%d", n);
        if (op[i] == m)
            printf(" * ");
        else if (op[i] == p)
            printf(" + ");
        else if (op[i] == s)
            printf(" - ");
        else if (op[i] == d)
            printf(" / ");
    }
    printf("%d = %d\n", n, target);
}

 

아래는 실행 결과. 7개의 9로 1234를 만들 수 있다.

아무래도 탐색 수가 많다보니 약 2~3초 정도 걸린다.