백준 10835. 카드게임

tose33 2023. 2. 9. 16:15

10835번: 카드게임

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오

www.acmicpc.net

문제의 핵심은 2차원 dp 배열을 만드는 것이다.

// i : 카드의 깊이
// j : LEFT or RIGHT
// dp[2][3] = 10 이라면 왼쪽 카드는 2번째 카드, 오른쪽 카드는 3번째, 그때의 점수는 10점
int dp[2010][2010];

현재 왼쪽 카드 LEFT와 오른쪽 카드 RIGHT가 각각 LEFT=i, RIGHT=j 라고 하면 [i][j] 이다.

왼쪽 카드만 버리는 경우에는 카드의 위치는 [i+1][j]가 된다.

양쪽 카드를 버리는 경우에는 카드의 위치는 [i+1][j]가 된다.
오른쪽 카드를 버릴수 있을때, 오른쪽 카드를 버리는 경우에는 카드의 위치는 [i][j+1] 이 된다.

이렇게 2차원 배열에 왼쪽 카드와 오른쪽 카드의 위치를 나타내고 점수를 저장한다.

dp배열을 최초에 -1로 초기화 해놓고,

카드를 버릴수만 있기 때문에 2중 루프를 1부터 N까지 순서대로 돌면서 dp[i][j]에 저장된 값이 0이상인 경우에만 계산해주면 된다.