[Python] 백준 14888번 : 연산자 끼워넣기

문제

14888번: 연산자 끼워넣기

[ 문제 조건 ]

• 입력
  1. N : 수의 개수
  2. A1 ~ An : 수들
  3. sum(N-1) : 합이 N-1인 4개의 정수, 연산자 4개의 각각 개수가 주어짐 (+,-,×,÷) 순으로
• 출력
  • 만들 수 있는 식의 최대 & 최소 값 출력
  • -10억 ≤ 결과값 ≤ 10억

[ 해결순서 ]

1. 백트래킹 유형은 dfs를 주로 사용하는 것 같아 dfs로 풀어보려고 했다.
2. 모든 경우의 수를 전부 구해 최대 최소를 비교하는 문제여서 어쨌든 모두 비교해서 구해야한다.
3. 1. 처음 먼저 plus가 1이니까 dfs가 걸려 깊이우선탐색 후 나머지 연산까지 깊이우선탐색 해 값을 갱신
   2. 깊이우선탐색 plus 연산은 끝났고, 나머지 연산 중 multiply 값이 1이므로 해당 연산 기준으로 재귀적으로 dfs 진행 후
   3. 최대, 최소 갱신 후 최종 갱신된 값이 정답이 될 것이다.예제 2를 분석해서 구해봤다.

[ 점화식 ]

dfs(depth+1, result+values[depth], plus, minus, multiply, divide)

✏️한줄평

: 생각한 대로 코드 짜기는 어렵다ㅜㅜ

---

코드