백준 알고리즘 14888_ 연산자 끼워넣기 C

문제

링크(14888번: 연산자 끼워넣기 (acmicpc.net))

14888번: 연산자 끼워넣기

 

사고과정

문제를 읽을 때 주의해야 하는 문제다. 처음 입력받은 숫자의 순서는 바뀌지 않고 연산자들의 순서만 바꾸면 된다. 즉 연산자들의 "중복이 있는 순서 세우기"이다. 문제는 어떻게 그 순서를 정할 것이냐는 것. 처음에 생각한 것은 연산배열을 선언해 숫자로 대치된 연산자를 저장해 모든 조합을 저장하는 것이다. 하지만 노력과 시간에 비해 결과가 좋지 않을 것 같아서 (되는지도 모르겠다) 깔끔하게 폐기했다. 이후 생각한 것은 재귀함수를 이용하는 것이다. 연산자의 순서를 지정하지 않고 모든 경우의 수를 탐색할 수 있는 가장 쉬운 방법이라고 생각했다.

 

내코드

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int add_num, minus_num, mul_num, dev_num, N;
int min, max;

void Calculate(int cal_count, int* numbers, int result, int add_count, int minus_count, int mul_count, int dev_count);

void add(int a, int b, int* numbers,int cal_count, int add_count, int minus_count, int mul_count, int dev_count) {
	if (add_count > add_num)return;

	Calculate(cal_count + 1, numbers, a + b, add_count , minus_count, mul_count, dev_count);
}
void minus(int a, int b, int* numbers, int cal_count, int add_count, int minus_count, int mul_count, int dev_count) {
	if (minus_count > minus_num)return;

	Calculate(cal_count + 1, numbers, a - b, add_count , minus_count , mul_count, dev_count);
}
void mul(int a, int b, int* numbers, int cal_count, int add_count, int minus_count, int mul_count, int dev_count) {
	if (mul_count > mul_num)return;

	Calculate(cal_count + 1, numbers, a * b, add_count , minus_count, mul_count , dev_count);
}
void dev(int a, int b, int* numbers, int cal_count, int add_count, int minus_count, int mul_count, int dev_count) {
	if (dev_count > dev_num)return;

	Calculate(cal_count + 1, numbers, a / b, add_count , minus_count, mul_count, dev_count );
}


void Calculate(int cal_count, int* numbers, int result,int add_count,int minus_count,int mul_count,int dev_count) {
	if (cal_count == N) {
		//printf("%d\n", result);            //각 연산을 마친 후 결과를 프린트해보세요
		if (result >  max)max = result;
		if (result < min)min = result;
		return;
	}

	add(result, numbers[cal_count], numbers, cal_count, add_count + 1, minus_count, mul_count, dev_count);
	minus(result, numbers[cal_count], numbers, cal_count, add_count, minus_count+1, mul_count, dev_count);
	mul(result, numbers[cal_count], numbers, cal_count, add_count, minus_count, mul_count + 1, dev_count);
	dev(result, numbers[cal_count], numbers, cal_count, add_count, minus_count, mul_count, dev_count + 1);
}


int main() {
	int i;
	scanf("%d", &N);
	int* numbers = (int*)malloc(N * sizeof(int));
	for (i = 0; i < N; i++) {
		scanf("%d", &numbers[i]);
	}
	scanf("%d %d %d %d", &add_num, &minus_num, &mul_num, &dev_num);

	min = INT_MAX;
	max = INT_MIN;
	Calculate(1, numbers, numbers[0], 0, 0, 0, 0);		//처음 들어가는 연산횟수는 1, 각 연산의 횟수는 0으로 넣는다

	printf("%d\n%d", max, min);	


	free(numbers);
	return 0;
}

먼저 입력변수를 전역변수로 선언한다. 전역변수로 선언하는 것을 선호하지 않음에도 이렇게 한 이유는 각 함수의 인자를 줄이고 싶었기 때문이다. 이후 Calculate함수를 불러온다. Calculate함수는 각 연산함수를 불러오는 함수이고, 연산횟수, 숫자배열, 결과, 각 연산을 실행한 횟수를 인자로 받아들인다. 이후 연산횟수 cal_count가 최대 연산횟수가 되면 이때까지의 연산결과를 max,min과 비교하여 각 값을 갱신한다. 종료조건을 만족하지 않는다면 4가지 연산을 따로 시행한다.

 

각 연산함수의 종료조건도 따로 지정해야 한다. 문제에서 각 연산의 횟수를 제시하기 때문이다. 이후 각 연산의 결과를 다시 Calculate할수의 인자로 전달한다. 

 

피드백

솔직히 각 함수의 전달 인자가 너무 복잡하고 많다. 함수간에 서로를 불러오는 형식이기 때문에 각 함수에서 사용하지 않는 인자도 모두 불러와줘야 하기 때문이다. 사실 함수를 2유형으로 쪼개지 않아도 Calculate함수 안에 조건문을 삽입하여 재귀적으로 호출하면 더 코드 수가 줄어들었을 것이다. 전역변수를 지양하는 것은 개인의 취향이라, 전역변수없이 함수를 좀더 간단히 하는 부분을 생각해 봐야겠다.