[백트래킹 + 구현] 백준 실버1 14888번: 연산자 끼워넣기(Swift)

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

14888번: 연산자 끼워넣기

문제풀이

해당 문제는 주어진 수와 연산자를 조합하여 최솟값과 최댓값을 구하는 문제이다.

최솟값과 최댓값을 구해야하므로 백트래킹 기법을 사용하여 모든 경우의 수를 탐색해야 한다.

let n = Int(readLine()!)!
var numArr: [Int] = readLine()!.split(separator: " ").map { Int($0)! }
var visited: [Int] = readLine()!.split(separator: " ").map { Int($0)! }
var resultMax = Int.min
var resultMin = Int.max

func dfs(_ count: Int, _ value: Int) {
  if count == n {
    resultMax = max(value, resultMax)
    resultMin = min(value, resultMin)
    return
  }
  
  for i in 0..<4 {
    if visited[i] != 0 {
      visited[i] -= 1
      var value = value
      if i == 0 {
        value += numArr[count]
      } else if i == 1 {
        value -= numArr[count]
      } else if i == 2 {
        value *= numArr[count]
      } else if i == 3 {
        value /= numArr[count]
      }
      dfs(count + 1, value)
      visited[i] += 1
    }
  }
}

dfs(1, numArr[0])
print(resultMax)
print(resultMin)

백트래킹 기법을 사용하기 위해 visited 배열을 통해 연산자의 개수를 카운팅 해준다.

또한, dfs 메서드를 구현하여 제귀를 활용해 모든 경우의 수를 탐색하면 된다.

파라미터로 어디까지 연산했는지 카운팅하고, value를 통해 지금까지 연산 값을 저장한다.

사용한 연산자는 visited 배열에서 하나 빼주고 다음 제귀를 통해 다음 연산을 진행한다.

모든 수의 연산이 끝났으면 값을 각 변수에 저장하고 제귀 함수를 끝낸다.

제귀함수가 끝나면 다음 경우의 수도 계산할 수 있게 visited를 원 상대로 복귀시킨다.