Guess Number Higher or Lower 2

문제: leetcode.com/problems/guess-number-higher-or-lower-ii/

Guess Number Higher or Lower II - LeetCode

 

 MINMAX 알고리즘을 사용하는 문제.  어떤 수를 선택하던 상관없이 무조건 이길 수 있는 최소의 돈의 양을 return 해야한다.

 

 from i to j에서 사이의 값인 k를 택했을 때 i ~ k -1과 k + 1 ~ j 중에서 최악의 경우의 수를 찾으면 된다.  가장 최악인 경우를 찾으면 해당 경우의 돈 만큼 가지고 있으면 무조건 이길 수 있다.

 

class Solution {
public:
    int dp[201][201];
    
    int guess(int i, int j){
        if(i >= j){
            return 0;
        }
        
        int & ret = dp[i][j];
        
        if(ret != -1){
            return ret;
        }
        
        int ans = INT_MAX;
        
        for(int k = i; k <= j; k++){
            ans = min(ans, k + max(guess(i, k - 1), guess(k + 1, j)));
        }
        return ret = ans;
    }
    
    int getMoneyAmount(int n) {
        memset(dp, -1, sizeof(dp));
        return guess(1, n);
    }
};

 i, j를 들어갈 때 이미 들어갔던 범위인 경우는 caching을 해준다.  

 

Time complexity: O(N^2)

Space complexity: O(N^2) - 2d array 선언도 있고, recursion stack frame의 범위가 N^2이다.