b11062. 카드 게임

 

https://www.acmicpc.net/problem/11062

 

 

 

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

 

---

 

📌 문제 개요

 

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

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

 

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

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

 

---

 

💡 예제 입력

1
4
4 7 2 9

 

---

 

✅ 예제 출력

13

 

---

 

🛠 알고리즘 접근 방식

 

• 구간 [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 설계 능력을 기를 수 있는 문제였습니다.