17825 주사위 윷놀이
문제 링크
배운 점
- Kotlin의 참조의 동일성(Referential equality) 비교 연산자
===
문제
- 처음에는 시작 칸에 말 4개가 있다.
- 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
- 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
- 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
- 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.
주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.
입력
첫째 줄 주사위에서 나올 수 10개가 순서대로 주어진다.
출력
얻을 수 있는 점수의 최대값을 출력한다.
-
오류 찾기 좋은 예제
입력
3 5 2 5 3 5 2 1 3 1출력
246 (말의 순서 : 1 2 2 1 1 1 1 1 2 1)
나의 풀이
실패한 풀이
- 최대값을 출력하는 재귀함수
gameSimulation() - 재귀함수의 결과가 최대값이 아니라고 생각함, 애초에 코드의 제약조건이 문제와 일치하지 않음
- 윷놀이의 중간 경로의 겹치는 구간에 대한 처리가 미흡함
- 외곽 구간 30과 내부 경로의 30에 대한 처리가 이뤄지지 않음
- 따라서, 출력된 말의 움직임을 실제로 해보면 겹쳐서 조건을 위반함
- 문제를 naive하게 읽으면 안된다.
- 외각의 score 부분의 처리는 옳았지만 내부 경로의 score 처리가 없다.
package baekjoon.kotlin.p17825
import java.util.*
import kotlin.math.max
private fun readNums() = readLine()!!.split(" ").map { it.toInt() }
private val board = Array(21) { (it) * 2 }
private val board10 = arrayOf(10, 13, 16, 19)
private val board20 = arrayOf(20, 22, 24)
private val board30 = arrayOf(30, 28, 27, 26)
private val board25 = arrayOf(25, 30, 35, 40)
private const val ARRIVED = -1000
fun main() {
val diceNumber = readNums()
val markers = Array(4) { Pair(0, board) }
board.forEach{print("$it ")}
println()
board10.forEach{print("$it ")}
println()
board20.forEach{print("$it ")}
println()
board30.forEach{print("$it ")}
println()
fun gameSimulation(currentDiceIndex: Int, curSum: Int): Int {
if (currentDiceIndex == 10) return curSum
val mv = diceNumber[currentDiceIndex]
var ret = curSum
markers.forEachIndexed { i, marker ->
if (marker.first != ARRIVED) {
var markerNew = (marker.first + mv) to marker.second
val markerSaved = marker.first to marker.second
var score = 0
if (markerNew.first >= markerNew.second.size) {
markerNew = ARRIVED to marker.second
} else {
score = markerNew.second[markerNew.first]
if(markerNew.second === board) {
when (score) {
10 -> markerNew = 0 to board10
20 -> markerNew = 0 to board20
30 -> markerNew = 0 to board30
}
}
}
if(markerNew.first != ARRIVED && markers.contains(markerNew)) {
return@forEachIndexed
}
markers[i] = markerNew
//ret = max(ret, score + gameSimulation(currentDiceIndex + 1))
var t = gameSimulation(currentDiceIndex + 1, curSum + score)
if(ret < t) {
ret = t
/*if(retArr[currentDiceIndex].third < ret) {
retArr[currentDiceIndex] = Triple(i, score, ret)
if(currentDiceIndex == 9 && i == 0 && score == 40 && ret == 40) {
println("!!!")
}
}*/
}
markers[i] = markerSaved
//or makers[i] = marker
}
}
return ret
}
println(gameSimulation(0, 0))
/*retArr.forEach {
println("${it.first} ${it.second} ${it.third}")
}*/
}
옳은 풀이
!!! 친 부분에 괄호를 제대로 닫지 않아 조건이 제대로 적용되지 않았다. 코드의 가독성에 신경써야 한다.
package baekjoon.kotlin.p17825
import kotlin.math.max
private fun readNums() = readLine()!!.split(" ").map { it.toInt() }
private val boardST = Array(21) { it * 2 }
private val board10 = arrayOf(10, 13, 16, 19, 25, 30, 35, 40)
private val board20 = arrayOf(20, 22, 24, 25, 30, 35, 40)
private val board30 = arrayOf(30, 28, 27, 26, 25, 30, 35, 40)
private const val ARRIVED = -1000
fun main() {
val moves = readNums()
val markers = Array(4) { Pair(0, boardST) }
fun dfs(cur: Int): Int {
if (cur == 10) return 0
val mv = moves[cur]
var ret = 0
markers.forEachIndexed { mIdx, marker ->
if (marker.first == ARRIVED) return@forEachIndexed
var newIdx = marker.first + mv
var newArr = marker.second
var score = 0
// 움직임이 배열을 벗어남 -> 도착
if (newArr.size <= newIdx) {
newIdx = ARRIVED
} else {
score = newArr[newIdx]
if (newArr === boardST) {
when (score) {
10 -> {
newArr = board10
newIdx = 0
}
20 -> {
newArr = board20
newIdx = 0
}
30 -> {
newArr = board30
newIdx = 0
}
}
}
// 조건문을 분리해서 깔끔하게 하는 것이 더 좋다.
if ((score in arrayOf(25, 35, 40) && score in markers.filter { it.first != ARRIVED }.map { it.second[it.first] }) ||
(score == 30 && ((newIdx == 0 && score in markers.filter { it.first != ARRIVED && it.second === board30 }.map { it.second[it.first] }) ||
(newIdx != 0 && score in markers.filter { it.first != ARRIVED && it.first > 0 }.map { it.second[it.first] })))) {
return@forEachIndexed
} else if (score == 22
&& score to newArr in markers
.filter { it.first != ARRIVED }.map { it.second[it.first] to it.second }) {
return@forEachIndexed
} /*else if (newArr !== boardST && score in markers
.filter { it.first != ARRIVED && it.second === boardST}.map { it.second[it.first] }) {
return@forEachIndexed
}*/
else if ((newIdx to newArr) in markers) {
return@forEachIndexed
}
// 개선판
if (score in arrayOf(25, 35, 40) && score in markers.filter { it.first != ARRIVED }.map { it.second[it.first] }) {
return@forEachIndexed
} else if (score == 30 && (
(newIdx == 0 && score in markers.filter { it.first != ARRIVED && it.second === board30 }.map { it.second[it.first] }) ||
(newIdx != 0 && score in markers.filter { it.first != ARRIVED && it.first > 0 }.map { it.second[it.first] }) // !!!
)) {
return@forEachIndexed
} else if (score == 22
&& score to newArr in markers
.filter { it.first != ARRIVED }.map { it.second[it.first] to it.second }) {
return@forEachIndexed
} /*else if (newArr !== boardST && score in markers
.filter { it.first != ARRIVED && it.second === boardST}.map { it.second[it.first] }) {
return@forEachIndexed
}*/
else if ((newIdx to newArr) in markers) {
return@forEachIndexed
}
}
markers[mIdx] = newIdx to newArr
ret = max(ret, dfs(cur + 1) + score)
markers[mIdx] = marker
}
return ret
}
println(dfs(0))
}
댓글남기기