boj 10835 : 카드게임

boj 10835 : 카드게임

이것도 간단한 DP문제.

a : 왼쪽카드뭉치 수열

b : 오른쪽 카드뭉치 수열

f(i, j) : 왼쪽 i번째, 오른쪽 j번째 카드일 때의 앞으로 얻을 수 있는 최대값

이렇게 두면.

1. f(i, j) = max( f(i + 1, j + 1), f(i + 1, j), f(i, j + 1) + b[j])

1.1 f(i + 1, j + 1) : 카드를 둘다 버릴 때

1.2 f(i + 1, j) : 왼쪽 뭉치만 버릴 때

1.3 f(i, j + 1) + b[j] : 오른쪽 뭉치만 버릴 때(이때는 왼쪽 카드보다 오른쪽 카드 값이 작아야함)