[알고리즘/문제풀이/BOJ 14888번/삼성 SW 역량 테스트 기출] 연산자 끼워넣기

연산자 끼워넣기 문제는 BOJ 14888번 문제이자 삼성 SW 역량 테스트 기출문제입니다.

가능한 모든 연산자의 순열을 찾기 위해서 백트래킹 기법을 활용하여 완전 탐색을 하는 것이 문제의 핵심입니다.

아래의 풀이에서는 연산자 배열을 정의한 후 0번 인덱스부터 N-2번 인덱스까지 순서대로 4가지 연산자를 채우며 가능한 모든 연산자 수열을 찾는 백트래킹 함수를 설계하였습니다.

문제를 풀면서 느낀 부분은 백트래킹 함수를 통해 완전 탐색을 할 때는 모든 경우를 일정한 기준에 따라 빠짐없이 분류할 수 있다면 문제를 쉽게 할 수 있다는 점입니다. 

추가적인 팁으로 int형 변수에서 max와 min의 초기값을 설정할 때 간단하게 987654321, -987654321로 대입하면 int형의 최대, 최소 수의 범위를 기억하지 않아도 빠르게 해결할 수 있다는 점입니다. max의 경우 문제에서 가장 작은 수가 0인지 혹은 음수인지 확인하는 것도 주의해주시기 바랍니다.(필자는 코드를 다 짜놓고도 이 부분을 대충 넘겨서 틀렸다는 슬픈 소문이...)

필자가 작성한 코드는 다음과 같습니다.

---

#include<stdio.h>
//https://ark-hive.tistory.com/manage
int N;
int number[100];
int add, sub, mul, div;

char op[100]; //연산자 순열이 저장될 공간

int max = -999999999, min = 999999999;
int result;

void final_processing() {
	result = number[0];
	for (int i = 0; i < N - 1; i++) {
		if (op[i] == '+')
			result = result + number[i + 1];
		else if (op[i] == '-')
			result = result - number[i + 1];
		else if (op[i] == '*')
			result = result * number[i + 1];
		else if (op[i]=='/')
			result = result / number[i + 1];
	}

	if (result > max)
		max = result;
	if (result < min)
		min = result;

	result = 0;

	return;
}

void backtracking(int order) {
	
	if (order == N - 1) {
		final_processing();
		return;
	}
	else {
		if (add != 0) {
			op[order] = '+';
			add -= 1;
			backtracking(order + 1);
			add += 1;
			op[order] = 0;
		}
		if (sub != 0) {
			op[order] = '-';
			sub -= 1;
			backtracking(order + 1);
			sub += 1;
			op[order] = 0;
		}
		if (mul != 0) {
			op[order] = '*';
			mul -= 1;
			backtracking(order + 1);
			mul += 1;
			op[order] = 0;
		}
		if (div != 0) {
			op[order] = '/';
			div -= 1;
			backtracking(order + 1);
			div += 1;
			op[order] = 0;
		}
	}
}

int main(void) {

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		scanf("%d", &number[i]);
	}
	scanf("%d %d %d %d", &add, &sub, &mul, &div);

	backtracking(0);//순열에 0개의 연산자가 결정됨. 실행 시점의 상황

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

문제의 지문은 다음 링크에서 확인하실 수 있습니다.

https://www.acmicpc.net/problem/14888