[재귀, 백트래킹] 연산자 끼워넣기(BOJ 14888)

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

어떻게 재귀로 해서 최대 최소값을 구하지?

생각나는것

-는 최대-최소 일때 최대값, 최소-최대 일대 최소값이 나올것이다.

나누기는 최대/최소 일때 최대값, 최소/최대 일때 최소값

곱하기는 최대*최대 일때 최대, 최소*최소 일때 최소

더하기는 최대+최대 일때 최대, 최소+최소 일때 최소

위와 같은 조건들만 생각난다.

 

그러나 저 조건을 활용할 방법은 생각이 안난다. 단순히 모든 경우의 수를 구하고 정렬해서 최대,최소 값을 구할 방법만 생각난다.

 

그러나 위 조건 말고 단순히 모든 경우의 수를 구하고 최소 최대 값만 찾으면 되는 문제임.

 

🎯 이 문제에선 DFS/백트래킹이 맞는 이유

• 연산자들의 순열(중복 가능)을 **끝까지 조합해 봐야 함**
• 연산이 끝나는 조건은 `N-1개 연산자`를 모두 사용했을 때
• 그래서 **"깊이 있게 들어가고 → 연산자 원상복구"** 를 반복하는 방식이 적합

 

🎯 왜 백트래킹을 쓰는가?

• 경우의 수가 많아도, 조건에 따라 가지치기(Pruning)가 가능해서
• DFS 구조에서 연산자 하나 쓸 때마다 감소시키고, 돌아올 때 복원하면
  → 불필요한 중복 계산을 피할 수 있음

---

예를 들어 이런 구조로 탐색:

모든 조합을 따라 내려가면서 최댓값/최솟값을 갱신하면 끝!

 

 

내가 생각한 조건을을 적용해서 알고리즘을 풀려고 한다면 이번 문제 보다는 아래와 같은 문제에서 핵심적으로 활용될 수 있음

 

• 괄호 추가하기 문제 → 계산 순서를 바꿀 수 있음
• 게임 트리 탐색 (MinMax) → 상대가 최대/최소 전략 쓸 때
• DP로 최댓값/최솟값 구하기 → 이 연산자 조건들이 핵심이 돼