[백준 14888] 연산자 끼워넣기 (C++)

문제에 대한 자세한 설명은 링크 참조

1. N개의 수가 주어지고 그 사이에 N-1개의 연산자를 넣으려고 함

2. N개의 수에 대한 연산자의 조합은 다음과 같이 삽입될 수 있다.

3. N-1개의 연산자는 +, -, ×, ÷로 각각 사용할 수 있는 수가 주어짐

4. 연산식 조합 중 최대와 최소를 만드는 것을 구하면 됨

* (중요) 여기서 연산자 우선순위는 무시되고, 연산식은 좌에서 우의 순서로 계산되면 된다.

DFS

주어진 연산자 갯수들을 이용하여 각 연산자들의 배치 조합을 DFS로 모두 만들고, 해당 연산식 중 최대와 최소를 업데이트하며 완전탐색한다.

* 만약 연산자 우선순위가 고려되어 평가한다면 스택을 이용하여 다음과 같이 구현할 수 있다.

요약하자면, 연산식을 평가할 때 좌에서 우로 스캔하며 낮은 우선순위의 연산자는 스택에 넣어 후순위로 연산하고, 높은 우선순위의 연산자는 선순위로 평가하여 스택에 그 결과를 삽입하는 것. 최종 결과는 크기 1인 스택의 Top에 남는 수.

1. DFS로 각 연산자들의 모든 배치 조합을 만듦

2. Base case(조합 완성) 도달 시, 해당 연산식을 평가하여 최대/최소 업데이트

Bloofer Blog