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

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

14888번: 연산자 끼워넣기

---

문제 풀이

 1. 피연산자와 연산자의 개수를 배열에 담는다.

 2. 연산자를 끼워넣는 함수를 실행한다.

  <함수 설명>

  함수 getans는 변수 cnt(피연산자의 index)와 변수 result(연산 결과)를 매개변수로 가진다. 

 변수 cnt 가 n의 값과 일치하면 최대, 최소를 비교하여 값을 최신화한다. 

 피연산자의 순서는 고정이 되어있기 때문에 다음에 올 연산자가 어떤 것인지만 결정하면 된다. 따라서 연산자 4개 중에 하나만 결정하면 되기 때문에 반복 횟수는 4가 된다.

 연산자 배열의 특정 값이 0이라면 코드를 건너뛴다. 값이 존재한다면 index를 통해서 +, -, ×, ÷ 중 어떤 것인지 판단하고 변수 result의 값을 계산해서 다시 함수 getans를 부른다(재귀 호출). 이때 사용한 연산자의 배열 값을 재귀 호출한 함수에서 다시 사용되는 것을 막기 위해 1 만큼 감소시킨다.

 재귀 호출이 끝나고 나면 다시 돌아가서 다른 경우를 따져보아야하기 때문에 사용한 연산자 배열 값을 다시 증가시킨다. 

느낀 점

 어떻게 구현할 것인가에 대한 방향은 맞았지만 실제로 구현하는 것은 조금 힘들었다. 처음에 스위치 문을 많이 사용해보지 않아 스위치 문으로 구현해보고 싶었지만 제대로 연산이 이루어지지 않아서 애 먹었고, 연산 결과를 벡터에 다 넣고 함수가 끝나면 벡터 중에서 최대, 최소를 찾는 구현을 해보려고 했지만 실패했다. 생각보다 시간이 더 걸려서 조건문으로 풀어 맞췄지만 생각한 대로 아직 100% 구현하지 못해서 너무 아쉽다.

코드

#include <iostream>
using namespace std;

int operands[11] = { 0, };
int operators[4] = { 0, };
int n;
int Max_result = -1000000001;
int Min_result = 1000000001;

void show() {
	cout << Max_result << " " << Min_result;
}

void getans(int cnt, int result) {
	if (cnt == n) {
		if (result > Max_result) Max_result = result;
		if (result < Min_result) Min_result = result;
		return;
	}
	for (int i = 0; i < 4;i++) {
		if (!operators[i]) continue;
		operators[i]--;
		if (i == 0)	getans(cnt + 1, result + operands[cnt]);
		else if (i == 1) getans(cnt + 1, result - operands[cnt]);
		else if (i == 2) getans(cnt + 1, result * operands[cnt]);
		else getans(cnt + 1, result / operands[cnt]);
		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];
	}
	getans(1, operands[0]);
	show();
}