Algorithm & Data Structures/BOJ
b11062. 카드 게임
Geisha
2025. 6. 4. 18:32
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 설계 능력을 기를 수 있는 문제였습니다.