연산자 끼워넣기

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

삼성 코딩 테스트 기출 문제이다.

시간 초과가 났다.

오답 풀이

다음의 예를 보자.

숫자 : 1 2 3 4 5 6

연산자 : 2 1 1 1

따라서 연산자는 다음과 같다.

+, +, -, *, /

경우의 수는 같은 것을 포함하는 순열이다.

5! / 2!

각각의 경우에 숫자를 이용해 계산을 하고, 계산 값들 중에 최소값, 최대값을 찾는다.

정답 풀이

시뮬렌이션 문제라고 생각했다.

해설을 보고 완전 탐색 문제란 것을 알았다. 따라서 BFS or DFS 로 풀 수 있다. 익숙한 BFS로 해결하였다.

다음의 예시에서 나올 수 있는 모든 경우의 수를 그림으로 그려보자.

숫자 : 1, 2, 3, 4

연산자 : +, +, *

문제에서 주어진대로, 숫자는 순서를 그대로 유지한다.

1 다음에 오는 숫자는 2다. 1과 2를 계산할 수 있는 연산자는 + 와 * 이다. 이 두 경우를 큐에 넣는다.

1+2 와 3 을 계산 할 수 있는 연산자는 +와 * 이다. 이 두 경우를 큐에 넣는다.

이와 같은 방식으로 모든 경우의 수를 큐에 넣는다.

모든 연산자를 사용 했을 때(트리의 마지막 depth)가 최종 결과값 이므로, 이들 중에 최대값 및 최소값을 구한다.