[백준] 10835 카드게임

---

카드를 조건에 맞게 제거하여 최대 점수를 구하는 문제이다. 문제 해결에 가장 중요한 규칙은 아래와 같다.

 

1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
3. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

처음 문제를 접할 때는 최대 점수를 구하기 때문에 그리디 방식으로 접근했다. 하지만 카드 뭉치가 소멸하는 순서가 점수와 관련이 없기 때문에 반복문을 전부 다 돌아야 했고 그리디로는 시간초과가 발생했다.

 

결국 풀지 못해 다른 분들이 작성한 풀이법을 참고하였다.

 

그리디가 아닌 다이내믹 프로그래밍으로 접근해야 해결되는 문제였다.

 

누적 점수를 담고 있는 d 배열을 -1로 초기화 한다. 만일 d 배열을 0으로 초기화 하게되면 1번 규칙에 의해서 점수를 얻지 못하는 경우가 발생하기 떄문에 이전이 이미 진행했던 경우를 또 다시 진행하는 일이 발생한다. 따라서 0이 아닌 -1로 초기화 한다.

 

그리고 규칙 1과 2의 경우를 나누어 d 배열의 값을 구한다

규칙1. d[l][r] = max(d[l][r+1] + right[r], d[l][r])

규칙2. d[l][r] = max(func(l+1, r), func(l+1, r+1))

 

소스 코드

from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 6)
readline = stdin.readline

N = int(readline())
left = [*map(int, readline().split())]
right = [*map(int, readline().split())]
d = [[-1] * N for _ in range(N)]

def dfs(l, r):
    if l >= N or r >= N:
        return 0
    
    if d[l][r] != -1:
        return d[l][r]
    
    if left[l] > right[r]:
        d[l][r] = dfs(l, r+1) + right[r]
    else:
        d[l][r] = max(dfs(l+1, r), dfs(l+1, r+1))

    return d[l][r]

print(dfs(0, 0))