✨ 자바로 푸는 카드 게임 문제 풀이

📌 문제 개요

백준 11062번 “카드 게임” 문제는

양 끝에서 카드를 번갈아 가져가는 두 플레이어가 있을 때, 첫 번째 플레이어가 얻을 수 있는 최대 점수를 계산하는 문제입니다.

이 문제는 두 사람 모두 최선의 선택을 할 때, 나의 점수를 최대화할 수 있는 방법을 찾아야 하므로,

전형적인 DP(다이나믹 프로그래밍) 문제입니다.

💡 예제 입력

1
4
4 7 2 9

✅ 예제 출력

🛠 알고리즘 접근 방식

구간 [s, e]에서 플레이어가 차례일 때,
최적의 선택을 했을 때 얻을 수 있는 점수를 dp[s][e]로 정의합니다.
합계 - 상대방 점수 방식으로 현재 플레이어 점수를 계산합니다.
prefix[i]: 0부터 i-1까지의 누적합을 저장해 구간합을 O(1)로 계산합니다.

✅ 핵심 아이디어

dp[s][e]를 구할 때 두 가지 선택지:
- 왼쪽 arr[s]를 고른 후 → 남은 구간은 [s+1, e]
- 오른쪽 arr[e]를 고른 후 → 남은 구간은 [s, e-1]
각 경우에서 상대가 가져갈 점수를 고려해 현재 플레이어 점수 최댓값을 선택

dp[s][e] = max(
    arr[s] + (총합 - arr[s] - dp[s+1][e]),
    arr[e] + (총합 - arr[e] - dp[s][e-1])
)

🧾 코드 해설

🎲 입력 처리 및 누적합 계산

int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int[][] dp = new int[N][N];
int[] prefix = new int[N + 1];

for (int i = 0; i < N; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
    dp[i][i] = arr[i]; // 카드 1장일 땐 그냥 선택
}

🧠 DP 점화식 계산

for (int len = 1; len < N; len++) {
    for (int s = 0; s + len < N; s++) {
        int e = s + len;
        int total = prefix[e + 1] - prefix[s]; // 구간합
        dp[s][e] = Math.max(
            arr[s] + (total - arr[s] - dp[s + 1][e]),
            arr[e] + (total - arr[e] - dp[s][e - 1])
        );
    }
}

✅ 핵심 포인트 정리

양쪽 끝 중에서 하나를 골라야 하므로 구간 DP로 해결
상대도 최적 전략을 쓴다는 전제하에 나의 최선 선택을 계산
누적합 prefix를 활용해 O(1)로 구간합을 계산

🌌 결론: 전략적 선택이 만든 최선의 결과

이 문제는 단순히 점수가 높은 카드를 고른다고 풀리지 않습니다.

상대의 다음 행동까지 예측하며 내 점수를 최대화해야 하는 점에서,

전략적 사고와 DP 설계 능력을 기를 수 있는 문제였습니다.