[백준] 14888번 연산자 끼워넣기 - c++

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

14888번: 연산자 끼워넣기

#include<iostream>

using namespace std;
int max_n= -1000000001;
int min_n = 1000000001;
int n;
int math[4];
int num[11];

void dfs(int answer ,int cnt) {

	if (cnt == n ) {
		if (answer >= max_n) {
			max_n = answer;
		}
		if (answer <= min_n) {
			min_n = answer;
		}
		return;
	}
	for (int i = 0; i < 4; i++) {
		if (math[i] > 0) {
			math[i] -= 1;
			if (i == 0) {
				dfs(answer + num[cnt], cnt + 1);
			}
			else if (i==1) {
				dfs(answer - num[cnt], cnt + 1);
			}
			else if (i == 2) {
				dfs(answer * num[cnt], cnt + 1);
			}
			else if (i == 3) {
				dfs(answer / num[cnt], cnt + 1);
			}
			math[i] += 1;
		}
	}
	return;
}
int main() {
	
	cin >> n ;
	for (int i=0; i < n; i++) {
		cin >> num[i];
	}
	for (int i=0; i < 4; i++) {
		cin >> math[i];
	}
	dfs(num[0], 1);

	cout << max_n << '\n';
	cout << min_n;
}

이 문제 파이썬으로도 풀었는데 c++로도 풀어봤다. 이문제를 풀면서 dfs를 확실히 익힐수 있다.

삼성전자 기출인 만큼 쉽지는 않다?

여기서 문제를 풀때 중요한것 

함수 중단조건과 각함수 연산자를 끼워넣는 생각

for (int i = 0; i < 4; i++) {
		if (math[i] > 0) {
			math[i] -= 1;
			if (i == 0) {
				dfs(answer + num[cnt], cnt + 1);
			}
			else if (i==1) {
				dfs(answer - num[cnt], cnt + 1);
			}
			else if (i == 2) {
				dfs(answer * num[cnt], cnt + 1);
			}
			else if (i == 3) {
				dfs(answer / num[cnt], cnt + 1);
			}
			math[i] += 1;
		}

이 부분이 아주 중요하다. 

왜 중요하냐?

여기가 연산의 핵심이기 때문이다.

우선 연산자가 존재할때만 해주도 for문을 돌리면서 모든 경우를 다 해준다.

여기서 연산자 사용하면 1만큼 줄여주고

if 문을 마지막가지 해주고 나서는 +1을 해준다

왜냐하면 우리는 입력했을때 1이상인 연산자만 사용할 거기 때문이다.

0인거는 아에 고려하지 않는다

그러면 위에서 연산자를 사용했는데 왜! +1 해줌?

이럴수 있는데 

왜냐? 이게 백트레킹 dfs 때문이다.

만약에 끝까지 가서 모든 연산자의 수가 0 0 0 0이 되고 cnt가 n 과 같아지면 함수를 리턴해주는데?

이때 함수가 종료되므로 이전에 실행 되었던 연산 값을 다시 복구 해줘야 다른 연산을 다시할수 있기 때문이다.

아무튼 이런식으로 풀면 끝이다.