[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 풀이를 작성하겠다.