[모의 SW 역량테스트 - 4008] 숫자 만들기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeRZV6kBUDFAVH&categoryId=AWIeRZV6kBUDFAVH&categoryType=CODE

SW Expert Academy

 

위 사이트에 로그인 하시면 문제를 볼 수 있습니다.

 

백준에도 괄호 추가하기라고 이 문제와 유사한 문제가 있다. 내 기억으로는 19년 8월 A형 역량 테스트 문제와 아주 유사하다고 들었다.

 

이런 류의 문제는 dfs로 백트래킹 하면서 완전탐색을 하면 된다.

 

크게 어렵지는 않았다.

 

- 풀이 방법

1. 입력을 받는다.

 

2. dfs로 완전 탐색을 돌린다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int t, n, min_num, max_num, res;
int number[12];
int oper[4]; //각 인덱스마다 +, -, *, /
int candi;

void dfs(int node) {
	if (node == n) {
		if (min_num > candi) min_num = candi;
		if (max_num < candi) max_num = candi;
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (oper[i] > 0) {
			oper[i] -= 1;
			int temp = candi;
			if (i == 0) candi += number[node];
			else if (i == 1) candi -= number[node];
			else if (i == 2) candi *= number[node];
			else if (i == 3) candi /= number[node];

			dfs(node + 1);

			candi = temp;
			oper[i] += 1;
		}
	}
}

int main(void) {

	scanf("%d", &t);

	for (int tc = 1; tc <= t; tc++) {

		res = 0;
		min_num = 0x7fffffff, max_num = -0x7fffffff;

		scanf("%d", &n);

		for (int i = 0; i < 4; i++) scanf("%d", &oper[i]);
		for (int i = 0; i < n; i++) scanf("%d", &number[i]);

		candi = number[0];
		dfs(1);

		res = max_num - min_num;
		printf("#%d %d\n", tc, res);
	}

	getchar();
	getchar();

	return 0;
}