(M - 375. Guess Number Higher or Lower II) Minmax

주어진 범위 [a, b] 내에서 임의의 root를 선택해서 BST를 만들어야 함.

[1, 10]이 주어졌다면, root로 1, 2, 3, ... , 10 등을 선택할 수 있고, 각각 다른 BST가 만들어지겠지?

 

만들어진 BST에서는 'trunk값'을 구할 수 있음 (root에서부터 leaf 직전까지 경로의 노드 합)

[1,10] 범위가 주어졌을 때, 7을 노드로 하면 trunk값이 11, 15, 16인 BST가 됨

 

우린 각 BST에서 max trunk값을 각각 뽑는다 (= 해당 게임을 이기는데 필요한 max money)

그 후, b-a+1개의 trunk값 중 min값을 선택한게 답 (= 이 값들로 게임을 이길 수 있으므로, 개중 가장 작은 min값 선택)

class Solution {
    int dp[201][201];
    // [start, end] 범위의 수에서 임의의 root를 정해 BST를 만든다.
    // end-start+1 개의 BST는 각각 max trunk값이 있을텐데, 그 중 min값을 반환
    // * trunk값 : root~leaf 까지의 값의 합인데 leaf만 제외
    int maxTrunk(int start, int end) {
        if (start >= end) return 0;
        
        int& ret = dp[start][end];
        if (ret) return ret;
        
        ret = numeric_limits<int>::max();
        for(int root = start; root <= end; root++){
            ret = min(ret, root + max(maxTrunk(start, root - 1), maxTrunk(root + 1, end)));
        }   
        
        return ret;
    }
    
public:
    int getMoneyAmount(int n) {
        return maxTrunk(1, n);
    }
};

 

범위가 주어졌을 때 maxTrunk 함수를 호출한다고 하면, 다음과 같은 상태 트리가 만들어진다. 

각 level마다 min, max를 번갈아가며 하위 레벨의 값을 선택한다 → minmax 알고리즘

Fig2. 범위 [1, 10]이 만드는 전체 상태 트리

 

minmax는 두 플레이어가 번갈아가며 '최선의 선택'을 할 때, 어떤 선택을 해야 내가 최선의 선택을 할 수 있는지 판단하는 알고리즘이다.

 

Leaf노드에서는 현재의 상태가 어떤 플레이어에게 유리한지 (favorable) 숫자 metric으로 표현한다.

이후 level을 올라가며, 한 플레이어는 min만, 다른 플레이어는 max만 써서 값을 선택하는 식으로 '최선의 선택'을 구현한다.

체스나 오목 AI에 쓰이는 알고리즘이라고 한다.

 

https://www.youtube.com/watch?v=l-hh51ncgDI 

내가 푼 LeetCode문제는 player가 explicit하게 명시된 문제는 아니어서 코드 모양이 다르지만,

상태 트리를 봤을 때 (Fig2), tree level별로 min-max가 번갈아가며 쓰인다.