Daily LeetCode Challenge - 1140. Stone Game II

Problem From.
https://leetcode.com/problems/stone-game-ii/

오늘 문제는 돌더미에서 bob 과 alice 하 한차례씩 돌아가면서 돌을 가져간다고 할때 alice 가 가져갈 수 있는 돌의 최대값을 구하는 문제였다. 돌을 가져가는데에는 규칙이 있는데, 처음 1~2개의 돌더미를 가져갈수 있고, 그 다음 차례 사람은 그 2배인 1~4개를 가져갈 수 있는 규칙이다.

이 문제는 memoization 을 이용하여 풀 수있었는데, alice 가 먼저 돌을 가져가는 경우를 각각 저장해두고, 그 다음 bob 이 돌을 가져가는 경우에서 각각의 최대값을 기록해나가면서, 마지막에 alice 의 돌이 가장 많아지는 선택지를 반환해주었다.

import kotlin.math.max

class Solution {
    val hm = HashMap<Pair<Int,Int>,Pair<Int,Int>>()

    fun stoneGameII(piles: IntArray): Int {
        val p = solve(piles, 0, 1)
        return p.first
    }

    fun solve(piles: IntArray, i: Int, m: Int): Pair<Int,Int> {
        if(i==piles.size){
            return Pair(0,0)
        }
        if(hm.containsKey(Pair(i,m))) {
            return hm[Pair(i,m)]!!
        }
        var friend = 0
        var enemy = 0
        var tmp = 0
        for(x in 1 until 2*m+1){
            if(i+x<=piles.size){
                tmp += piles[i+x-1]
                val p = solve(piles, i+x, max(x,m))
                if(tmp+p.second > friend) {
                    friend = tmp + p.second
                    enemy = p.first
                }
            } else {
                break
            }
        }
        val ans = Pair(friend, enemy)
        hm[Pair(i,m)] = ans
        return ans
    }
}