LeetCode – Guess number higher or lower II

출처 :https://harunscorner.wordpress.com/2016/09/04/leetcode-guess-number-higher-or-lower-ii-solution/

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

n = 3일 경우를 예로해서 문제를 풀어보자. 3가지의 선택을 할수 있다 1,2,3 중에 한개를 선택하는 것이다.

1을 선택할 시에는 2개의 경우가 생긴다.

• Case X : 1이 정답일 경우 0$을 지불한다. 아니면

• Case Y : 1이 정답이 아닐 경우 1$를 지불 한다. (이 경우에는 1< 정답 임을 알 수 있다. 왜냐하면 1이 정답이 아닐 경우 1보다 작거나 큰 경우 중 하나가 정답일 텐데 1보다 작은 수는 없으므로 ) 그리고 (2, 3) 부분 문제를 가지게 된다.

  재귀적으로 1을 선택했던 방법과 같은 방법을 적용하면서 2 또는 3을 선택할 수 있다. 2를 선택했다면 2가지 결과를 얻게 된다. 2가 실제 정답이면 0$지불 한다. 2가 실제 정답이 아니면 2$를 지불하고 3이 남았음으로 3이 정답임을 알게 된다. 달리 말하면 만약 3을 선택했을 경우에는 3이 정답의 경우 이거나 아니면 3$ 를 지불하고 2만 남았음으로 2가 정답임을 알게되는 것이다.

  이것을 정리 하면, 2를 선택했을때 최악의 경우 2$ 를 지불하고 3을 선택 했을때 최악의 경우 3$ 를 지불하는 것이다. 그래서 우리는 최악의 경우에 최소로 돈을 지불하는 2$를 지불하는 2를 선택한다. (2를 선택했을때 2가 답이 아니면 2$지불이고, 3을 선택을때 3이 답이 아니면 3$ 지불이기 때문에 2$불 가지고 2를 선택하는것이 더 이득이 된다? minmax 알고리즘?) 그래서 2가 (2,3) 부분 문제의 답이 된다. 결국 이 경우의 총 지불되는 비용은 1$+2$ = 3$ 이 된다.

초기에 2를 선택할 경우를 생각해보면. 2개의 가능한 결과를 가진다.

• 2가 정답일 경우 0$을 지불한다. 아니면
• 2가 이 정답이 아닐 경우 2$를 지불 한다. 이 경우에는, 정답은 2보다 작거나 크거나 둘중에 하나일 것이다. 왜냐하면 남아 있는 값이 크거나 작거나 두개만 남아 있음으로. 그러므로 또 다시 guess할 필요 없이 2$ 만을 지불하고 끝나게 된다. 그래서 처음에 2를 선택했을 시에는 2$ 만을 지불하면 된다.

초기에 3을 선택할 경우를 생각해보면

• 3가 정답일 경우 0$을 지불한다. 아니면
• 3가 이 정답이 아닐 경우 3$를 지불 한다. 이 경우에 1을 선택했을때 ( (2,3)의 부분문제를 해결할때) 와 유사하게 (1,2) 부분 문제를 가지게 된다. 1또는 2를 선택 할 수 있는데. 1을 선택하는 경우 1이 정답이면 0$ 을 지불고 끝이난다. 1이 실제 정답이 아니면 1$ 을 지불하고 답은 2가된다. 2를 선택한는 경우에 2가 정답이면 0$ 을 지불하고, 2가 정답이 아니면 2$ 를 지불하고 1이 정답이 된다. 이 경우에도 1선택해서 틀렸을 경우 1$ 을 지불하는 것이 2선택해서 틀렸을 경우 2$ 지불하는 것 보다 이득이므로 1을 선택한다. (1,2 ) 부분 문제의 답은 1 그래서 3을 선택했을때 틀렸을 경우의 값는 1$ + 3$ = 4$ 이 된다.

위의 3가지 경우 중에 가장 최소의 값이 답이 됨으로 n= 3일 경우에 답은 2가 된다.

위의 경우를 재귀 + memoization으로 코딩하면 아래와 같다.

class Solution {
public:
    
    
    int **dp;
    const int MAX_VALUE = 987654321;    
    
    int solve(int start, int end) {

        if(start >= end)
            return 0;
    
        if(dp[start][end] != MAX_VALUE)
            return dp[start][end];
        
        //설명과 같이 현재 상태에서 한개씩 선택하고 선택된것과 선택 안된
        // 영역의 값을 더해서 그값중에 큰값 (최악의 경우)선택한다.
        // 그리고 그 값들 중에 가장 적은 값을 dp에 지정하여 최적값을 구한다.
        for(int i = start; i <= end; i++) {
            
            dp[start][end] = 
              min(dp[start][end], max(i+solve(start,i-1),i+solve(i+1,end)));
        }

        return dp[start][end];
        
    }
    
    int getMoneyAmount(int n) {

        dp = new int*[n+1];
        
        for(int i = 0; i < n+1; i++) {
            dp[i] = new int[n+1];
        }

        for(int i = 0; i < n+1; i++) {
        
            for(int j = 0; j < n+1; j++) {
                dp[i][j] = MAX_VALUE;            
            }
        }
    
        return solve(1,n);
        
    }
};