[C언어] 14888번 연산자 끼워넣기 (삼성 SW 역량 테스트 기출 문제)

[문제]

정해진 개수의 연산자를 임의의 순서대로 배치하여 앞에서부터 연산을 수행했을 때(피연산자의 순서는 바꾸지 않는다.) 최대인 경우와 최소인 경우를 구하는 문제이다.

 

[해결 방법]

 

1. 같은 연산자도 여러개 포함할 수 있기 때문에 겹치는 부분을 어떻게 생략할 수 있는지를 생각해야한다. 굳이 생략하지 않고, 모두 다른 연산자들이라고 생각해도 문제를 풀 수는 있지만, 시간이 매우 오래 걸릴것 같아서 같은 경우의 수를 생략하는 방식으로 가야할 것 같다. 다음 그림은 + 두개, - 두개가 있을 때 연산자를 배열하는 모든 경우를 나타낸 것인데, 어떤 연산자가 있을때 그 뒤에 올 수 있는 모든 종류의 연산자를 붙이는 과정을 반복하여 배열하는 것이다.

 

 

 

2. 이제 숫자를 계산하는 함수를 작성해야한다. 예를 들어서 + 2개, * 1개, - 1개가 있고, 숫자는 1,3,1,2,5가 있다고 하자. 맨 앞 피연산자인 1은 그대로 가져온다. 계산하는 힘수가 calc라고 할 때, 1과 3을 더하고, 곱하고, 빼고, 나눈 결과를 각각 calc의 함수의 인자에 담아 넘겨주되, 모두 사용하거나 없는 연산자(여기에서는 나누기)를 이용한 연산 결과는 넘겨주지 않는다. 추가로, 현재 인덱스의 1을 더해 다음 인덱스로 넘겨준다. 남은 연산자 횟수는 연산 횟수 전 1을 빼준 뒤 연산 수행 후 다시 1을 더해 돌려준다. 만약 인덱스가 N과 같을 경우 모든 연산이 끝난 것이므로 이 결과를 최대, 최솟값과 비교해준다.

 

다음 그림은 숫자 배열이 1,3,1,2,5이고, 이번에 수행할 연산 순서는 더하기->곱하기->빼기->더하기 일때 연산이 수행되는 과정이다.

 

이를 이용해서 만든 연산 함수이다.(ops : 연산자 개수 배열, arr : 피연산자 배열)

void calc(int prev_result, int index, int N) {
	if (index == N) {
		// 이때 prev_result == 총 연산 결과이다. 여기에 최대, 최소 비교 기능을 넣어준다.
	}
	else {
		for (int i = 0; i < 4; i++) {
			if (ops[i] > 0) {
				ops[i]--;
				switch (i) {
				case 0:
					calc(prev_result + arr[index], index + 1, N);
					break;
				case 1:
					calc(prev_result - arr[index], index + 1, N);
					break;
				case 2:
					calc(prev_result * arr[index], index + 1, N);
					break;
				case 3:
					calc(prev_result / arr[index], index + 1, N);
					break;
				}
				ops[i]++;
			}
		}
	}


}

 

 

[완성된 코드]

#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>

int ops[4];
int* arr;
int max = 0;
int min = 0;
int flag = 0;
void calc(int prev_result, int index, int N) {
	if (index == N) {
		if (flag == 0 || max < prev_result) {
			if (prev_result == 54) {
				printf("");
			}
			max = prev_result;
		}
		if (flag == 0 || min > prev_result) {
			min = prev_result;
			flag = 1;
		}
		//printf("%d\n", prev_result);
	}
	else {
		for (int i = 0; i < 4; i++) {
			if (ops[i] > 0) {
				ops[i]--;
				switch (i) {
				case 0:
					calc(prev_result + arr[index], index + 1, N);
					break;
				case 1:
					calc(prev_result - arr[index], index + 1, N);
					break;
				case 2:
					calc(prev_result * arr[index], index + 1, N);
					break;
				case 3:
					calc(prev_result / arr[index], index + 1, N);
					break;
				}
				ops[i]++;
			}
		}
	}


}



int main()
{
	int N;
	scanf("%d", &N);
	arr = (int*)malloc(sizeof(int) * N);
	for (int* p = arr; p < arr + N; p++) {
		scanf("%d", p);
	}
	for (int i = 0; i < 4; i++) {
		scanf("%d", ops + i);
	}
	calc(arr[0], 1, N);
	printf("%d\n", max);
	printf("%d\n", min);
}