[백준 10835] 카드게임 (Python) (맞왜틀)

👩🏻‍💻문제링크

[백준 10835] 카드게임 (Python) (맞왜틀)

✍️Idea Sketch

언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.

백준을 풀면서 "맞았습니다!"가 아니라 "**점" 점수를 매겨주는 문제는 이 문제가 처음이다.
문제를 풀면서 맞왜틀을 정말 많이 외쳤다.

다이나믹 프로그래밍 Top-down 방식으로 구현했다.
당신이 31점이라면 - 메모이제이션 없이 구현했을 것이고
당신이 64점이라면이라면 - sys.setrecursionlimit(10**6)을 생략했거나 dp배열을 0으로 초기화했을 것이다.

👩🏻‍💻 sys.setrecursionlimit()

Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어지면, RecursionError가 발생한다.
이 경우 최대 재귀 깊이를 변경하면 된다.
BOJ 채점 서버는 최대 재귀 깊이가 1,000이다.

  import sys
  sys.setrecursionlimit(10**6)

참고
https://help.acmicpc.net/judge/rte/RecursionError
https://fuzzysound.github.io/sys-setrecursionlimit

👩🏻‍💻 이 문제는 dp배열을 -1로 초기화해야하는 이유

dp배열을 0으로 초기화하고 + 메모이제이션에서 0을 탐색 유무의 flag로 쓰는 경우 문제가 생긴다.

  if dp[x][y] != 0:  # 0이 아닌 경우, 이미 탐색했다고 판단하여 dp배열의 값을 반환한다.
    return dp[x][y]

탐색 결과 0을 반환하는 경우, 이미 탐색했는데도 dp배열의 값이 그대로 0이기 때문에
탐색되지 않았다고 판단할 수 있다.
따라서 시간초과가 발생할 수 있다.

참고
https://www.acmicpc.net/board/view/38906
https://www.acmicpc.net/board/view/15769

👩🏻‍💻 표 그리기

이 문제는 표를 직접 그려보고 나서야 제대로 이해했다.
백준 예제 입력 1번은 다음과 같다.

  3
  3 2 5
  2 4 1

dfs(왼쪽 *번째 카드, 오른쪽 *번째 카드)
dfs(0, 0)은 왼쪽 첫번째 카드, 오른쪽 첫번째 카드를 의미한다.

  dfs(0, 0) = dfs(0, 1) + 2                    # 왼쪽 3 > 오른쪽 2 이므로 오른쪽 2 버리고 점수 획득
  dfs(0, 1) = max(dfs(1, 1), dfs(1, 2))        # 왼쪽 3 < 오른쪽 4 이므로 max(왼쪽 버리기, 둘 다 버리기) 구하기
  dfs(1, 1) = max(dfs(2, 1), dfs(2, 2))        # 왼쪽 2 < 오른쪽 4 이므로 max(왼쪽 버리기, 둘 다 버리기) 구하기
  dfs(2, 1) = dfs(2, 2) + 4                    # 왼쪽 5 > 오른쪽 4 이므로 오른쪽 4 버리고 점수 획득
  dfs(2, 2) = dfs(2, 3) + 1                    # 왼쪽 5 > 오른쪽 1 이므로 오른쪽 1 버리고 점수 획득
  dfs(2, 3) = 0                                # 오른쪽 네번째 카드는 없으므로 0 반환
  ...
  따라서 dfs(2, 2) = dfs(2, 3) + 1 = 1
  dfs(2, 1) = dfs(2, 2) + 4 = 5
  dfs(1, 1) = max(dfs(2, 1), dfs(2, 2)) = max(5, 1) = 5
  ...(중략)...
  위와 같은 연산 과정을 거친다.

	right[y]	2	4	1
left[x]	x \ y	0	1	2
3	0	7	5	-1
2	1	-1	5	1
5	2	-1	5	1

left는 왼쪽 더미 카드, right는 오른쪽 더미 카드이다.
x, y는 각각 left, right의 인덱스이며 0부터 시작한다. 0이 첫번째 카드이다.

✍️소스코드

import sys
sys.setrecursionlimit(10**6)

def dfs(x, y):
  if x >= n or y >= n:
    return 0

  if dp[x][y] != -1:
    return dp[x][y]

  if left[x] > right[y]:
    dp[x][y] = dfs(x, y+1) + right[y]  # 오른쪽 버리기
  else:
    discard_left = dfs(x+1, y) 
    discard_both = dfs(x+1, y+1) 
    dp[x][y] = max(discard_left, discard_both)  # max(왼쪽 버리기, 둘 다 버리기)

  return dp[x][y]


if __name__ == "__main__":  
  n = int(input())
  left = list(map(int, sys.stdin.readline().rstrip().split()))
  right = list(map(int, sys.stdin.readline().rstrip().split()))

  dp = [[-1 for _ in range(n)] for _ in range(n)] 
  dfs(0, 0)
  print(dp[0][0])