[BOJ][14888] 연산자 끼워넣기

문제 : www.acmicpc.net/problem/14888

---

N의 범위가 2~11 이다. 백트래킹으로 돌려도 될만한 시간이다.

정수집합을 앞에서부터 탐색해가면서 가능한 부호를 모두 돌려봐서 나오는 수들 중 최대값, 최소값을 구한다.

pair<int, int> answer;

// arr : 정수형 배열
// signCnt : 부호 개수,
// ind : arr 탐색 중인 인덱스
// result : 이때까지 계산한 결과값
// sign : arr[ind]에 적용할 부호. arr[ind] 앞에 들어갈 부호
void backtracking(int[] arr, int[] signCnt, int ind, int result, int sign) {
	// 경계값 확인
    sign 부호 확인
    	+ 인 경우: result += arr[ind]
        - 인 경우: result -= arr[ind]
        * 인 경우: result *= arr[ind]
        / 인 경우: result /= arr[ind]

	// 정답 갱신
    answer = 기존 answer 값과 result 비교 후 최대값, 최소값 갱신
    
    for(int sign=0; sign<signCnt.size(); sign++){
    	signCnt[sign]이 0개 이하라면 더 이상 사용 불가능 -> 다음 for문 확인
        signCnt[sign] -= 1;
        // 현재 기호 넣고 ind+1 인덱스 확인하는 재귀함수 호출
        backtracking(arr, signCnt, ind+1, result, sign); 
        signCnt[sign] += 1;
    }
	
}

처음 시작은 0에서 +arr[0]이기 때문에

backtracking(arr, signCnt, 0, 0, PLUS);

sign에 PLUS를 넣고 호출한다.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/BOJ/14888.%20%EC%97%B0%EC%82%B0%EC%9E%90%20%EB%81%BC%EC%9B%8C%EB%84%A3%EA%B8%B0.cpp