[Swift] 백준_연산자 끼워넣기(14888)

문제

 

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

14888번: 연산자 끼워넣기

 

 

풀이

 

숫자의 순서가 고정되어있고, 연산자의 우선순위 없이 계산한다는 얘기가 중요했던 것 같다.

즉, 연산자의 순서만 바꿔주면 되고 앞에서부터 연산을 하면 된다는 얘기이다.

 

평소처럼 check나 visited대신 이번에는 연산자가 사용되는 것이므로 oper[i] -= 1을 해줬다. 그리고 i에 따라서 어떤 연산자인지 알 수 있으므로 if 문을 이용해 각각 다른 current로 dfs함수를 호출하였다.

 

숫자는 고정되어있으므로 depth라는 파라미터를 이용해 어떤 숫자와 current를 계산할지 알 수 있게하였고, 이 depth를 이용해 종료 조건을 설정해주었따.

 

문제에서 최대값과 최소값이 주어졌으므로 아예 최대값은 최소값인 -10억으로, 최소값은 10억으로 초기화를 하여 비교를 바로 할 수 있도록 하였다.

import Foundation

let n = Int(readLine()!)!
let numbers = readLine()!.split(separator: " ").map { Int(String($0))! }
var oper = readLine()!.split(separator: " ").map { Int(String($0))! }
var maxResult = -1000000000
var minResult = 1000000000

func dfs(_ current: Int, _ depth: Int) {
    if depth == n {
        maxResult = max(maxResult, current)
        minResult = min(minResult, current)
        return
    }
    for i in 0...3 {
        if oper[i] != 0 {
            oper[i] -= 1
            if i == 0 {
                dfs(current + numbers[depth], depth + 1)
            } else if i == 1 {
                dfs(current - numbers[depth], depth + 1)
            } else if i == 2 {
                dfs(current * numbers[depth], depth + 1)
            } else {
                dfs(current / numbers[depth], depth + 1)
            }
            oper[i] += 1
        }
    }
}
dfs(numbers[0],1)
print(maxResult)
print(minResult)

 

 

_____________________________________________________________________________________________________

 

 

안쓰는 변수를 안지우고 제출해서 다시 지우고 제출하니 시간이 줄어들었다. 잘 확인하자.