728x90

삼성 SW 역량 테스트 기출 문제이자 단계별로 풀어보기 백트래킹의 7단계 문제

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

www.acmicpc.net

처음에 분명히 맞게 풀었는데 컴파일 에러가 나는 것이었다. 원인은 min과 max라는 변수 이름 때문이었다.

따라서 min을 minn으로, max를 maxx로 바꿔줬더니 성공

#include <iostream>
using namespace std;

int n;
int* numbers;
int maxx = -1000000000;
int minn = 1000000000;

void select(char* oper, int num, int plusRemain, int minusRemain, int multiplyRemain, int divideRemain) {
	if (num == n - 1) {
		int result = numbers[0];
		for (int i = 0; i < n - 1; i++) {
			switch (oper[i]) {
			case '+':
				result += numbers[i + 1]; break;
			case '-':
				result -= numbers[i + 1]; break;
			case '*':
				result *= numbers[i + 1]; break;
			case '/':
				result /= numbers[i + 1]; break;
			}
		}
		if (result > maxx) maxx = result;
		if (result < minn) minn = result;
		return;
	}
	if (plusRemain > 0) {
		oper[num] = '+';
		select(oper, num + 1, plusRemain - 1, minusRemain, multiplyRemain, divideRemain);
	}
	if (minusRemain > 0) {
		oper[num] = '-';
		select(oper, num + 1, plusRemain, minusRemain - 1, multiplyRemain, divideRemain);
	}
	if (multiplyRemain > 0) {
		oper[num] = '*';
		select(oper, num + 1, plusRemain, minusRemain, multiplyRemain - 1, divideRemain);
	}
	if (divideRemain > 0) {
		oper[num] = '/';
		select(oper, num + 1, plusRemain, minusRemain, multiplyRemain, divideRemain - 1);
	}
}

int main() {
	cin >> n;
	numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int plus, minus, multiply, divide;
	cin >> plus >> minus >> multiply >> divide;
	char* oper = new char[n - 1];
	select(oper, 0, plus, minus, multiply, divide);	
	cout << maxx << endl;
	cout << minn << endl;
	return 0;
}
728x90

+ Recent posts