BEAKJOON

백준(14888번 연산자 끼워넣기)풀이 C++

Shin_jisoo 2021. 1. 22. 18:54
728x90

www.acmicpc.net/problem/14888

 

14888번: 연산자 끼워넣기

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

www.acmicpc.net

1) 주석 없는 VERSION

#include<iostream>

using namespace std;

int N;
int operands[11];
int operators[4];
int mmin = 100000001;
int mmax = -1000000001;

void getanswer(int result, int idx) {

	if (idx == N) {
		if (result > mmax)
			mmax = result;
		if (result < mmin)
			mmin = result;
		return;
	}

	for (int i = 0;i < 4;i++) {

		if (operators[i] > 0) {

			operators[i]--;

			if (i == 0) 
				getanswer(result + operands[idx], idx + 1);
			else if (i == 1) 
				getanswer(result - operands[idx], idx + 1);
			else if (i == 2) 
				getanswer(result * operands[idx], idx + 1);
			else
				getanswer(result / operands[idx], idx + 1);

			operators[i]++;
		}
	}
	return;
}


int main() {
	cin >> N;

	for (int i = 0;i < N;i++) {
		cin >> operands[i];
	}

	for (int i = 0;i < 4;i++) {
		cin >> operators[i];
	}

	getanswer(operands[0], 1);
	cout << mmax << '\n';
	cout << mmin;

}

 

2) 주석 있는 VERSION

#include<iostream>

using namespace std;

int N;
int operands[11];
int operators[4];
int mmin = 100000001;
int mmax = -1000000001;

void getanswer(int result, int idx) {

	if (idx == N) {
		if (result > mmax)
			mmax = result;
		if (result < mmin)
			mmin = result;
		return;
	}

	for (int i = 0;i < 4;i++) {

		if (operators[i] > 0) {

			// 연산자 개수 줄여줌
			operators[i]--;

			if (i == 0) 
				getanswer(result + operands[idx], idx + 1);
			else if (i == 1) 
				getanswer(result - operands[idx], idx + 1);
			else if (i == 2) 
				getanswer(result * operands[idx], idx + 1);
			else
				getanswer(result / operands[idx], idx + 1);

			// 다른 연산자를 사용할 것이므로 줄였던 연산자 개수 늘려줌
			operators[i]++;
		}
	}
	return;
}


int main() {
	cin >> N;

	// 숫자 입력
	for (int i = 0;i < N;i++) {
		cin >> operands[i];
	}

	// 연산자 개수 입력
	for (int i = 0;i < 4;i++) {
		cin >> operators[i];
	}

	// 함수 호출
	getanswer(operands[0], 1);
	cout << mmax << '\n';
	cout << mmin;

}