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

문제

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

14888번: 연산자 끼워넣기

풀이

백트래킹 알고리즘을 사용해서 풀 수 있는 문제입니다.
수 사이에 연산자를 하나씩 다 넣어보고, 최대값과 최소값을 구할 수 있습니다.

연산자의 갯수를 Int 자료형의 Array로 입력을 주기 때문에,
이 Array의 Index를 사용해 어떤 연산자인지 판별하였습니다.

코드를 직접 보시면 쉽게 이해가 될 것입니다.

소스코드

	let n = Int(readLine()!)!
	let nums = readLine()!.split(separator: " ").map { Int($0)! }
	var opersCount = readLine()!.split(separator: " ").map { Int($0)! }
	var maxValue = Int.min
	var minValue = Int.max
	func dfs(answer: Int, d: Int) {
	if d == n {
	maxValue = max(maxValue, answer)
	minValue = min(minValue, answer)
	return
	}
	for i in 0..<4 {
	if opersCount[i] < 1 {
	continue
	}
	opersCount[i] -= 1
	switch i {
	case 0:
	dfs(answer: answer + nums[d], d: d + 1)
	case 1:
	dfs(answer: answer - nums[d], d: d + 1)
	case 2:
	dfs(answer: answer * nums[d], d: d + 1)
	case 3:
	dfs(answer: answer / nums[d], d: d + 1)
	default:
	break
	}
	opersCount[i] += 1
	}
	}
	dfs(answer: nums[0], d: 1)
	print(maxValue)
	print(minValue)

view raw 연산자 끼워넣기.swift hosted with ❤ by GitHub

후기

생각보다는 어려웠던 문제였습니다.
백트래킹 알고리즘은 금방 떠올렸는데, 구현하는데 시간이 조금 걸렸던 문제였습니다.