[백준] 14888번: 연산자 끼워넣기

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

14888번: 연산자 끼워넣기

 

문제 이해

숫자가 최대 11개 주어진다는 것은 연산자는 최대 10개라는 뜻이다.

연산자의 순서를 정하는 것이기 때문에 DFS를 이용해서 모든 경우의 수를 탐색하면 된다.

연산자의 개수가 정해져있으니까, 그 배열에서 하나씩 빼가면서 고르고, 다 고른 후에 계산을 해보면 된다.

곱셈, 나눗셈 우선이 아니므로 간단하게 앞에서부터 계산해주면 된다.

음수/양수 나눗셈의 경우 음수를 양수로 바꾼 후 나누고, 그 값을 다시 음수로 바꿔야 하니까 별도의 함수를 만들어주었고 나머지 연산은 그냥 기본 연산자를 사용했다.

 

주의할 점은 max와 min의 값인데, min은 당연 최댓값인 0x7fffffff로 주면 되지만 max의 경우에는 음수의 경우도 있기 때문에 그 범위를 정하기 좀 애매해보인다. 하지만 문제에서 최소 -10억이라고 했으니까 -10억 이하의 수로 지정해주면 된다.

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 11
#define ABS(x) (((x)>0)? (x):-(x))

int N;
int num[MAXN+5];
int op[4];
int max = -1999999999, min = 0x7fffffff;
int sel[MAXN + 5];

void Get_Input(void) {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &num[i]);
	}
	for (int i = 0; i < 4; i++) {
		scanf("%d", &op[i]);
	}
}

int divide(int a, int b) {
	// b는 항상 양수
	int res = ABS(a) / ABS(b);
	if (a > 0) return res;
	if (a < 0) return (-1) * res;
}

int Calculate(void) {
	int res;
	if (sel[0] == 0) res = num[0] + num[1];
	else if (sel[0] == 1) res = num[0] - num[1];
	else if (sel[0] == 2) res = num[0] * num[1];
	else res = divide(num[0], num[1]);

	for (int i = 1; i < N - 1; i++) {
		if (sel[i] == 0) res += num[i+1];
		else if (sel[i] == 1) res -= num[i+1];
		else if (sel[i] == 2) res *= num[i+1];
		else res = divide(res, num[i+1]);
	}
	return res;
}

void DFS(int cnt) {
	
	// 종료
	if (cnt == N - 1) {
		// N-1 개의 연산자 순서를 정했다.
		int res = Calculate();
		if (res > max) max = res;
		if (res < min) min = res;
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (op[i] <= 0) continue;
		sel[cnt] = i;
		op[i] -= 1;
		DFS(cnt + 1);
		op[i] += 1;
	}
}

int main(void) {
	Get_Input();
	DFS(0);
	printf("%d\n%d", max, min);
	return 0;
}