[Algorithm🧬] 백준 10835 : 카드게임

문제

처음에 생각한 BFS

왼 / 왼 오 / 오 를 버리는 경우를 전체 탐색한다고 생각했는데, 이렇게 하면 문제에서 상황이 그렇게 진행될 수 없는데 가지를 가버리는 경우가 생김...

import sys
from collections import deque

readl = sys.stdin.readline


def sol():
    global max_count
    q = deque()

    q.append((0, 0, 0))
    # visited[0][0] = 1

    while q:
        l, r, score = q.popleft()
        print(l, r, score)

        if l == n or r == n:
            break

        for i in range(3):
            if r >= l and i == 1: # 오른쪽이 더 크거나 같으면 오른쪽만 버리는건 안됨.
                continue

            dl, dr = adj[i]
            nl = dl + l
            nr = dr + r
            if not 0 <= nl < n:
                continue
            if not 0 <= nr < n:
                continue

            max_count = max(max_count, score + right[nr])
            q.append((nl, nr, score + right[nr]))



# 1. 왼쪽은 언제나 버릴 수 있음. 왼오 다 버려도 됨. 점수 X
# 2. 오른쪽 수 < 왼쪽 수 이면 오른쪽만 버릴 수 있음. 오른쪽만 버리면 오른쪽 카드에 적힌 수만큼 점수를 얻음.
# 3. 왼오 중 한 쪽이라도 남는 더미가 없으면 게임 끝.
# 게임을 진행했을 때 나올 수 있는 최댓값을 찾아라. -> DP ?

n = int(readl())
left = list(map(int, readl().split()))
right = list(map(int, readl().split()))

adj = [(1, 0), (0, 1), (1, 1)] # 왼쪽 버림, 오른쪽 버림, 왼오 버림

visited = [[0] * n for _ in range(n)]


max_count = 0

sol()

print(max_count)

DFS

import sys
from collections import deque

readl = sys.stdin.readline


def DFS(l, r, score):
    global max_score

    if l == n or r == n:
        max_score = max(max_score, score)
        return


    if left[l] > right[r]: 
        # 왼오 버리거나
        # 오른쪽만 버릴 수 있는데,
        # 이 게임에서는 오른쪽을 최대한 많이 버리는게 스코어에 이득이니까 왼오 버리는건 고려 X
        DFS(l, r + 1, score + right[r])
    else:
        # 아닌 경우에는 점수는 못얻고, 왼 / 왼오 버릴 수 있으니
        # 둘 다 버려보고 좋은 쪽으로 선택
        DFS(l + 1, r, score)
        DFS(l + 1, r + 1, score)



# 1. 왼쪽은 언제나 버릴 수 있음. 왼오 다 버려도 됨. 점수 X
# 2. 오른쪽 수 < 왼쪽 수 이면 오른쪽만 버릴 수 있음. 오른쪽만 버리면 오른쪽 카드에 적힌 수만큼 점수를 얻음.
# 3. 왼오 중 한 쪽이라도 남는 더미가 없으면 게임 끝.
# 게임을 진행했을 때 나올 수 있는 최댓값을 찾아라. -> DP ?

n = int(readl())
left = list(map(int, readl().split()))
right = list(map(int, readl().split()))

max_score = 0

DFS(0, 0, 0)

print(max_score)

DP 64점 이라서 뭔가 했는데..

sys.setrecursionlimit(10**6) 을 추가해서 파이썬 재귀 깊이를 바꿔주면 되는 거였다.. 앞에 BFS DFS 둘 다 가능한데 DFS 했다가 RecursionError 났던 문제들도 이걸로 하면 가능할듯...

import sys
from collections import deque

sys.setrecursionlimit(10**6)

readl = sys.stdin.readline

def DP(l, r):
    if l == n or r == n:
        return 0

    # 이미 계산된 값이면 그 값을 return
    if dp[l][r] != -1:
        return dp[l][r]

    dp[l][r] = 0
    if right[r] < left[l]:
        dp[l][r] += right[r] + DP(l, r + 1)
    else:
        dp[l][r] += max(DP(l + 1, r), DP(l + 1, r + 1))

    return dp[l][r]


n = int(readl())
left = list(map(int, readl().split()))
right = list(map(int, readl().split()))

dp = [[-1] * n for _ in range(n)]


print(DP(0, 0))