백준 14888번 연산자 끼워넣기 (삼성 SW 역량테스트 기출문제)

문제 링크: https://www.acmicpc.net/problem/14888

사용한 알고리즘: Brute Force(완전탐색) ,DFS...?


 문제에서 주어진 숫자가 작아서 어렵지 않게 해결할 수 있는 문제였습니다.
N이 최대 11 이므로 Brute Force(완전탐색)을 썼습니다.
탐색하는 방법으로는 DFS를 사용했습니다.

문제를 푸는 과정은 다음과 같습니다.

(1) 우선 순서대로 주어지는 덧셈, 뺄셈, 곱셈, 나눗셈의 수를 저장합니다.
이후 DFS를 돌릴 함수를 만듭니다. 이 함수는 두번째 숫자부터 마지막 숫자까지 볼 것입니다. 첫번째 숫자는 함수를 돌리기 시작할 때 넣어줍니다.
함수를 돌리는 과정에서 4칙연산의 남은 수들과 중간 계산값(temp)을 들고 가면서, 각 4칙연산을 시행할 횟수가 남았으면, 그 연산을 시행한 후 연산의 남은 횟수를 -1 한 것을 다시 DFS로 돌려줍니다. 이때 중간 계산값이 10억과 -10억 밖으로 나가면 시행을 중단합니다.

DFS의 시간복잡도가 O(V+E)이고, 문제에서 숫자(V)를 최대 11로 주었고, DFS를 한번 돌릴때 마다 숫자간의 연산(E)이 4줄기로 뻗어 나가므로 최대 E = 4^10 라고 생각됩니다.
즉 O(11+4^10)으로(아마..?) 잘 돌아갑니다.

	#include <bits/stdc++.h>
	using namespace std;
	const long long MIN = -1000000000;
	const long long MAX = 1000000000;
	// Brute Force
	int N, arr[100], A, B, C, D;
	long long maxans = MIN;
	long long minans = MAX;
	void MakeAns(int curr, int c1, int c2, int c3, int c4, long long temp){
	if(temp<MIN||temp>MAX) return;
	if(curr==N){
	maxans = max(maxans,temp);
	minans = min(minans,temp);
	return;
	}
	if(c1>0) MakeAns(curr+1,c1-1,c2,c3,c4,temp+arr[curr]);
	if(c2>0) MakeAns(curr+1,c1,c2-1,c3,c4,temp-arr[curr]);
	if(c3>0) MakeAns(curr+1,c1,c2,c3-1,c4,temp*arr[curr]);
	if(c4>0) MakeAns(curr+1,c1,c2,c3,c4-1,temp/arr[curr]);
	}
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i)
	cin >> arr[i];
	cin >> A;
	cin >> B;
	cin >> C;
	cin >> D;
	MakeAns(1,A,B,C,D,arr[0]);
	cout << maxans << '\n';
	cout << minans << '\n';
	return 0;
	}

view raw BOJ 14888.cpp hosted with ❤ by GitHub