[백준 14888] 연산자 끼워넣기 cpp

문제 
N개의 수로 이루어진 수열이 있을 때 N-1개의 연산자를 수와 수사이에 끼워넣어 연산을 진행한다. 이때 최솟값과 최댓값을 구하라. 
단, 수는 이동할 수 없으면 식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행한다. 또한 나눗셈은 정수 나눗셈으로 몫만 취한다.

입력
첫째 줄에 수의 개수 N(2이상 11이하)
둘째 줄에는 N개의 수열을 입력
셋째 줄에는 합이 N-1인 4개의 정수가 주어지며 차례대로 덧셈, 뺄셈, 곱셈, 나눗셈의 개수를 의미한다.

출력
첫째 줄에 최댓값
둘째 줄에 최솟값

---

입력받은 수열은 고정이고 연산자의 개수 안에서 조합하여 최댓값, 최솟값을 출력해야한다.

따라서 두 가지를 고려해봐야 했다.

1. 연산자를 선택하는 조합

2. 조합된 연산자를 통해 수를 계산하기

 

연산자의 모든 경우의 수를 어떻게 뽑아낼 수 있을까?

아직 이러한 조합을 출력해내는 것은 백트래킹 밖에 떠오르지 않는다. 연산자의 개수가 포함되어 있는 배열을 for문으로 탐색하여 아직 사용할 수 있는 연산자가 남아있다면 해당 연산자를 사용한다.

 

여기서 수열에 저장되어 있는 숫자와 계산을 할 수 있다. 현재까지의 계산결과와 해당 연산자로 다음 수와 결과를 내면 될 것이다. 따라서 백트래킹을 하기위한 함수의 매개변수에는 현재까지의 계산결과, 현재까지 선택한 연산자의 개수를 넘겨주면서 모든 경우의 수를 탐색하도록 한다.

#include "pch.h"
#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;

int N;
int numbers[11];
int oper[4];
int ansMax = -1000000000;
int ansMin = 1000000000;

void solution(int total, int picked) {
	if (picked == N - 1) {
		ansMax = max(ansMax, total);
		ansMin = min(ansMin, total);
		return;
	}

	for (int i = 0; i < 4; i++) {
		if (oper[i] > 0) {
			oper[i]--;
			if (i == 0) {
				solution(total + numbers[picked + 1], picked + 1);
			}
			else if (i == 1) {
				solution(total - numbers[picked +1], picked + 1);
			}
			else if (i == 2) {
				solution(total*numbers[picked + 1], picked + 1);
			}
			else {
				solution(total / numbers[picked + 1], picked + 1);
			}
			oper[i]++;
		}
		
	}
}
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> numbers[i];
	}

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

	solution(numbers[0], 0);
	cout << ansMax << endl;
	cout << ansMin << endl;
	
	return 0;
}

 

느낀점

처음에 연산자의 경우의 수를 탐색하는 방법은 여러가지가 떠올랐다. 하지만 이것을 수와 계산까지 어떻게할지 계속 고민을 하였다. 이 문제를 통해 상태가 변하는 것과 변하지 않는 것으로 나눈다면 쉽게 접근이 가능할 수도 있겠다는 생각을 하였다.