문제
풀이 언어
kotlin
코드
import java.lang.Integer.max
import java.lang.Integer.min
import java.util.*
var n = 0
var max_value = Int.MIN_VALUE
var min_value = Int.MAX_VALUE
lateinit var array: Array<Int>
lateinit var operator: Array<Int>
fun main() = with(Scanner(System.`in`)) {
n = nextInt()
array = Array(n) { nextInt() }
operator = Array(4) { nextInt() }
calculate(array[0], 1)
println(max_value)
println(min_value)
}
fun calculate(sum: Int, index: Int) {
if (index == n) {
max_value = max(sum, max_value)
min_value = min(sum, min_value)
return
}
for (i in 0..3) {
if (operator[i] > 0) {
operator[i]-- // 연산자 줄이고
when (i) {
0 -> calculate(sum + array[index], index + 1)
1 -> calculate(sum - array[index], index + 1)
2 -> calculate(sum * array[index], index + 1)
3 -> calculate(sum / array[index], index + 1)
}
operator[i]++ // 연산자 다시 돌려놓고
}
}
}
풀이 방법
이번 문제는 백트래킹
보다는 DFS
에 가깝다. 둘이 개념적으로 매우 유사하지만 이번 문제의 경우 가지치기
없이 모든 경우에 대해 탐색하고 있기에 DFS라고 판단했다. (operator[i] > 0
조건을 가지치기로 본다면 백트래킹에 해당한다고도 볼 수 있다.)
+, -, *, %
연산을 모두 진행하면 된다. 중요한 점은 연산자 개수를 다시 돌려놔야 한다는 것이다.
결과
'✍️ 코테 준비 > Back Tracking' 카테고리의 다른 글
[백트래킹 / Kotlin] BOJ 1759 - 암호 만들기 (0) | 2022.04.10 |
---|---|
[백트래킹 / Kotlin] BOJ 1987 - 알파벳 (0) | 2022.04.10 |
[백트래킹 / Kotlin] BOJ 2580 - 스도쿠 (0) | 2022.03.30 |
[백트래킹 / Kotlin] BOJ 9663 - N Queen (0) | 2022.03.29 |
[백트래킹 / Kotlin] BOJ 15649 ~ 15652 - N과 M (1 ~ 4) (0) | 2022.03.28 |