[leetcode / medium] 486. Predict the Winner - (backtracking && dp) (Java)

[leetcode / medium] 486. Predict the Winner

🙋‍♂️ 들어가며

문제를 읽어보면 우리는 다음과 같이 이해할 수 있다.

p1, p2 존재

각자의 점수는 0점에서 시작하는데 p1부터 먼저 시작하고, 다음차례가 p2, 그다음 p1, 그다음 p2 이런식으로 돌아간다

각 차례마다 선수는 양 끝 숫자중 1개를 고르고 그때마다 숫자배열크기 1감소, 선수들은 각각 고른 숫자를 본인 점수에 추가하는데 더이상 고를게 없을때까지 진행한다.

p1이 이기면 true

p1, p2 점수가 같아도 p1 승리로 간주하여 true로 변환

그렇다면 p2가 이기는 상황으로 p1이 절대 이길 수 없다면 false

조건

• nums.length <= 20
• 숫자 최대크기 10,000,000

아이디어 최악의 실행시간 2^20 으로 조합이 가능하다고 생각하였고,

p1은 맨왼쪽꺼를 고르나, 맨 오른쪽을 고르며 번갈아가는 선택을 해도 둘중 1개라도 이긴다면 승리로 간주

p2는 p1의 승리를 위해 둘다 true일 필요가 있었다.

이에 다음과 같은 설계 구상을 하였다

static boolean back_tracking(~~)
    // 1. 만약 turn을 다돌았을때, 
        // 1-1. 만약 p1점수가 p2보다 크거나 같다면 true
        // 1-2. p2점수가 더 크다면 false (기본 고정값)

    // 2. 만약 p1 차례일 때
        // 2-1. 왼쪽이나, 오른쪽을 선택하는 재귀 형태의 left, right 각각 생성
        // 2-2. 만약 왼쪽이나, 오른쪽에서 재귀를 수행했을때, 1개라도 p1이 승리하면 true
    
    // 3. 그렇지않고, p2 차례일 때 
        // 3-1. 위와 같다.
        // 2-2. p2의 경우 p1이 무조건 승리하게 만들어야하기 때문에, left, right 둘다 true 일것

    // 4. (기본값 반환) false -> 어떤 경우에도 p1이 p2를 이길 수 없다면? 

✅ 정답 코드 (backtracing)

class Solution {
    public boolean predictTheWinner(int[] nums) {
        int N = nums.length;
        int sum_p1 = 0;
        int sum_p2 = 0;
        int s = 0;
        int e = N-1;
        int turn = 0;
        
        // 1. 조합 (2^20)
        boolean answer = comb(nums, s, e, sum_p1, sum_p2, turn);

        // 2. 결과 (p1이 이겼다면 true)
        if (answer) {
            return true;
        }
        // 3. p2가 이겼다면 false
        return false;
    }


    // 4. 조합 함수
    static boolean comb(int[] nums, int s, int e, int sum_p1, int sum_p2, int turn) {
        // 4-1. 만약 모든 차례가 끝났다면?
        if (s > e) {
            // 4-1-a. p1의 점수가 크거나 같다면?
            if (sum_p1 >= sum_p2) {
                return true;
            }
            // 4-1-b. p2의 점수가 더 크다면?
            return false;
        }
        
        // 4-2. p1부터 먼저 시작
        if (turn % 2 == 0) {
            
            // 4-2-a. 왼쪽 선택 (왼쪽 인덱스 증가)
            boolean left = comb(nums, s+1, e, sum_p1 + nums[s], sum_p2, turn+1);

            // 4-2-b. 오른쪽 선택 (오른쪽 인덱스 감소)
            boolean right = comb(nums, s, e-1, sum_p1 + nums[e], sum_p2, turn+1);

            // 4-2-c. p1은 왼쪽에서 출발하나 오른쪽에서 출발하나 많은 경로 중에 1개만이라도 이기면 됨
            if (left == true || right == true) {
                return true;
            }
        }
        // 4-3. p2 차례
        else if (turn % 2 == 1) {

            // 4-3-a. 왼쪽 차례 (왼쪽 인덱스 증가)
            boolean left = comb(nums, s+1, e, sum_p1, sum_p2 + nums[s], turn+1);

            // 4-3-b. 오른쪽 차례 (오른쪽 인덱스 감소)
            boolean right = comb(nums, s, e-1, sum_p1, sum_p2 + nums[e], turn+1);

            // 4-3-c. p1이 이길려면 p2 차례의 left, right 재귀도 둘다 true일것
            if (left == true && right == true) {
                return true;
            }
        }

        // 4-4. 어떤 경우라도 p1이 이길 수 없다면?
        return false;
    }

}

DP 풀이

우선 testcase {1, 5, 233, 7} 기준 p1이 승리하려면 1, 233을 선택해야한다.

우선 플레이어가 1명일때, 가능한 최대점수를 먼저 입력한다.

그 이후 p1, p2는 각각 최선의 선택을 하니까, 둘의 점수 차이를 왼쪽에서 골랐을 때랑, 오른쪽에서 골랐을 때 저장하자

만약 길이 3일때 왼쪽에서 먼저 고른다면 nums[left] - DP[1][2], 만약 오른쪽에서 먼저 고른다면 nums[right] - DP[0][1]

이제 계산해보자

# 길이 2일때
DP[0][1] = 4
DP[1][2] = 228
DP[2][3] = 226

# 길이 3일때
DP[0][2] = 229
DP[1][3] = -221

# 길이 4일떄
DP[0][3] = Math.max(left - DP[1][3], right - DP[0][2]);

✅ 정답 코드 (DP)

class Solution {
    public boolean predictTheWinner(int[] nums) {
        
        // 1. 값 차이를 저장하는 DP
        int N = nums.length;
        int[][] DP = new int[N][N];
        for (int i = 0; i < N; i++) {
            DP[i][i] = nums[i];
        }

        // 2. 왼쪽을 고르면, 맨 왼쪽 제외 i+1 ~ N-1
        // 오른쪽을 고르면 맨 오른쪽 제외 i ~ N-2
        for (int i = 2; i < N+1; i++) {
            for (int left = 0; left + i -1 < N; left++) {
                int right = left + i - 1;
                int pick_left = nums[left] - DP[left+1][right];
                int pick_right = nums[right] - DP[left][right-1];

                DP[left][right] = Math.max(pick_left, pick_right);
            }
        }

        // 3. 값차이가 양수라면 P1 승리로 간주
        if (DP[0][N-1] >= 0) {
            return true;
        }

        // 4. 기본값 반환 
        return false;
    }
}