[SWEA] #4008 _ 숫자 만들기

[숫자 만들기] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

가능한 모든 경우의 연산자 순서를 고려하여 숫자를 얻을 수 있다.

dfs를 이용하여 조합을 구해 해당 문제를 풀 수 있다.

 

나는 next_permutation을 이용하여 간단히 구현하였다.

next_permutation을 사용할 때 벡터의 초기 값은 작은 숫자에서 큰 숫자로 정렬되어 있어야 한다.

따라서, sort함수를 이용하여 연산자를 오름차순으로 정렬해주었다.

 

[ 소스 코드 ]

#include <cstdio>
#include <vector>
#include <algorithm>
#define MAX 12
#define INF 100000000

using namespace std;

int N, max_val, min_val;
int oper[4], num[MAX];
vector<char> v_oper;

void init();
void solve();
void initVector();
int calcNum(char op, int num1, int num2);
int main() {
	int T;
	
	scanf("%d", &T);
	for (int i = 1; i <= T; i++) {
		scanf("%d", &N);
		for (int j = 0; j < 4; j++) scanf("%d", &oper[j]);
		for (int j = 0; j < N; j++) scanf("%d", &num[j]);

		init();
		solve();

		printf("#%d %d\n", i, max_val - min_val);
	}

	return 0;
}

void init() {
	max_val = -INF;
	min_val = INF;
	v_oper.clear();
}

void solve() {
	initVector();
	sort(v_oper.begin(), v_oper.end());

	do {
		int result = num[0];
		for (int i = 0; i < N - 1; i++) {
			result = calcNum(v_oper[i], result, num[i + 1]);
		}
		min_val = min(min_val, result);
		max_val = max(max_val, result);
	} while (next_permutation(v_oper.begin(), v_oper.end()));
}

void initVector() {
	for (int i = 0; i < oper[0]; i++) v_oper.push_back('+');
	for (int i = 0; i < oper[1]; i++) v_oper.push_back('-');
	for (int i = 0; i < oper[2]; i++) v_oper.push_back('*');
	for (int i = 0; i < oper[3]; i++) v_oper.push_back('/');
}

int calcNum(char op, int num1, int num2) {
	switch (op) {
	case '+': return num1 + num2;
	case '-': return num1 - num2;
	case '*': return num1 * num2;
	case '/': return num1 / num2;
	}
}