1. 문제 설명
https://www.acmicpc.net/problem/10835
10835번: 카드게임
첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오
www.acmicpc.net
이 문제.. 바보같이 sys.setrecursionlimit = 10**7 이라고 입력해놓고 '왜 자꾸 틀렸지??'하고 샷건치던 문제였다..
2. 아이디어
문제가 엄청나게 길지만 요약하면 결국 둘 다 버리거나, 경우에 따라 왼쪽만 버릴거냐, 오른쪽만 버릴거냐를
판단하고 최댓값을 알아보라는 문제다. (두 줄 요약인데 진짜 이게 다다)
이번에도 '모든 경우의 수 중에~', '가장 ~한 값을 찾아라'라는 유형이므로 dp를 쓰면 될 것이다.
그리고 조건은 왼쪽, 오른쪽이 중요하므로 dp[왼쪽][오른쪽] = 최댓값 정도로 두면 끝난다.
놀랍게도 dp를 사용하는 알고리즘 문제는 대부분 이런 식이라..많이 풀어보면 골드까지는 대충 보인다.
bfs가 안 되는 이유가 긴가민가해서 문제를 다시 읽어봤더니
카드가 최대 좌우 2000개씩 들어올 수 있고, 그럼 2000 * 2000 크기의 그래프가 그려지는데
하나 방문할 때마다 큐에 좌표가 3개씩 들어간다.
어찌저찌 값의 비교를 통해 큐에 들어가는 좌표를 최소화 한다고 하더라도 최악의 경우에는
비교가 먹히지 않을 수도 있으므로..아니 이러면 메모리 초과가 나야 정상아닌가? 모르겠다.
어쨌든 이런 이유로 bfs로는 커버가 안 됐었던 것 같다.
bfs가 안 되면? dfs를 쓰면 된다. 깊이는 어차피 최대 4000이니까.
L [3, 2, 5, 6], R [2, 4, 1, 3]인 카드패가 있다고 가정하자.
cache는 모두 방문하지 않았음을 의미하는 -1로 초기화 시키고 dfs를 돌린다.
그렇다고 무작정 들어갈 것이 아니라 문제 조건을 고려해보자.
left > right인 경우에는 오른쪽 카드만 버릴 수 있으므로 col만큼 1 이동할 수 있고,
right <= left인 경우에는 row만큼 1 혹은 row, col 모두 1만큼 대각선 이동할 수 있다.
그리고 그 중에서 최댓값을 고르면 되는 것이다.
즉, dfs는 이런 식으로 움직인다.
가장 깊숙히 이동해서 n범위를 오버하면 재귀를 빠져나오면서 버렸던 카드값을 체크하면서 회귀환다.
column을 이동할 때는 그 값을 누적시키지만, 대각선이동이나 row이동은 누적시키지 않는다.
단, [0][1]인덱스 처럼 두 개의 값이 상이한 경우에 더 큰 값을 저장한다.
따라서 정답은 10이 출력될 것이다.
3. 코드
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def dfs(cache, left, right, n):
if left >= n or right >= n:
return 0
if cache[left][right] != -1:
return cache[left][right]
if a[left] > b[right]:
cache[left][right] = dfs(cache, left, right+1, n) + b[right]
else:
throw_both = dfs(cache, left+1, right, n)
throw_left = dfs(cache, left+1, right+1, n)
cache[left][right] = max(throw_both, throw_left)
return cache[left][right]
def solution():
cache = [[-1]*n for _ in range(n)]
dfs(cache, 0, 0, n)
print(cache[0][0])
solution()