[백준 11062]https://www.acmicpc.net/problem/11062
문제 조건
근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.
근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오.
예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 처음에 4가 적힌 카드를 가져가고, 명우는 3이 적힌 카드를 가져간다. 그리고 근우는 2가 적힌 카드를 가져가고, 명우는 마지막으로 1이 적힌 카드를 가져간다. 이때 근우와 명우는 최선의 전략으로 임했으며, 근우가 얻는 점수는 6이다.
문제 입력
입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.
각 테스트케이스 마다 첫 줄에는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 왼쪽에서 i번째에 놓인 카드에 적힌 수를 의미한다. 카드에 적혀있는 수는 1이상 10,000이하다.
문제 풀기 전 설계
최대 값을 구하기 위해선 이전 구간합에 현재 고를 카드의 점수를 더해야 한다는 점에서 문제에서 DP(Dynamic Programming)의 느낌이 강하게 든다. DP 문제 유형 중 유명한 냅색문제처럼 이 문제도 2차원 배열에 구간합을 저장하면 좋을 것이다.
문제 코드
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ_11062 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int tc = Integer.parseInt(br.readLine());
while (tc-- > 0) {
int n = Integer.parseInt(br.readLine());
int[] cards = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) cards[i] = Integer.parseInt(st.nextToken());
int[][] dp = new int[n + 2][n + 1];
// 마지막 카드가 근우의 것인지
boolean turnK = (n % 2 == 1);
for (int i = 1; i <= n; i++) { // i = 선택할 수 있는 카드의 개수
for (int j = 1; j + i - 1 <= n; j++) {
/*
left = 시작 인덱스
right = 끝 인덱스
dp[left][right] = left 번째 카드부터 ~ right 번째 카드까지 남았을 때 근우가 얻는 최대 점수
즉 정답은 dp[1][n]을 출력하면 됨.
*/
int left = j;
int right = j + i - 1;
/*
turnK = 근우의 턴
문제에서 서로 최선의 수를 고르기 때문에
근우의 턴일 경우 dp[i][j] = dp[i + 1][j] + 가장 왼쪽(cards[i]) 카드의 값과 dp[i][j - 1] + 가장 오른쪽(cards[j]) 카드의 값 중 큰 값
명우의 턴일 경우 dp[i][j] = dp[i + 1][j], dp[i][j - 1] 중 작은 값 + 0
*/
if (turnK) {
dp[left][right] = Math.max(dp[left + 1][right] + cards[left], dp[left][right - 1] + cards[right]);
} else {
dp[left][right] = Math.min(dp[left + 1][right], dp[left][right - 1]);
}
}
turnK = !turnK;
}
sb.append(dp[1][n]).append('\n');
}
System.out.println(sb);
}
}
문제 풀이
n이 짝수라면 마지막 카드는 명우가 가져가고, n이 홀수라면 마지막 카드는 근우가 가져간다.
dp[i][j] = i ~ j번째 카드가 남았을 때 근우가 얻은 점수의 최대값으로 둔다면 dp[1][n]이 답이 된다.
dp[i][j]를 구하기 위해서는 dp[i + 1][j]와 dp[i][j - 1]을 알아야 한다.
둘 다 최선의 수를 선택하기 때문에 cards[idx] = idx번째 카드의 점수라고 하면
근우 턴 : dp[i][j] = Max(dp[i + 1][j] + cards[i], dp[i][j - 1] + cards[j])
명우 턴 : dp[i][j] = Min(dp[i + 1][j] + cards[i], dp[i][j - 1] + cards[j])
이 된다.
[4, 3, 1, 2] 의 순서로 놓아진 카드 4장의 경우를 표를 이용해 설명하자면
마지막 카드는 명우가 가져가기 때문에 1장 남은 경우에는 모두 0점이다.
dp[1][2] = dp[1][1] + 3과 dp[2][2] + 4 중 큰 값인 4이다.
dp[2][3] = dp[2][2] + 1과 dp[3][3] + 3 중 큰 값인 3이다.
dp[3][4] = dp[3][3] + 2과 dp[4][4] + 1 중 큰 값인 2이다.
dp[1][3] = dp[1][2]과 dp[2][3] 중 작은 값인 3이다.
dp[2][4] = dp[2][3]과 dp[3][4] 중 작은 값인 2이다.
마지막으로 dp[1][4] = dp[1][3] + 2과 dp[2][4] + 4 중 큰 값인 6이 된다.
[4, 3, 1, 2, 5] 의 순서로 놓아진 카드 5장의 경우도 표로 표현하면 아래와 같다.
근우의 턴과 명우의 턴일 때 점수를 어떻게 처리할 지 생각하는 것이 가장 중요한 포인트이다.
Review
오랜만에 dp 문제를 풀어서 그런지 문제 푸는데 생각한 것보다 훨씬 오래 걸렸다.
dp 문제를 풀 때에는 두 가지만 기억하자
배열의 형태 = 답을 결정하기 위해 고려되어야 할 요소의 개수 (현재 문제는 답을 구하기 위해서는 왼쪽 끝 인덱스와 오른쪽 끝 인덱스 두 가지가 고려되어야 하기 때문에 2차원 배열)
이전에 구한 값을 어떻게 사용할 수 있을지 (점화식의 형태로 표현 가능하도록)
