백준 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)으로(아마..?) 잘 돌아갑니다.