[Python] 백준 10835 카드게임

문제 링크 : https://www.acmicpc.net/problem/10835

10835번: 카드게임

1. 접근 방법

각 차례마다 할 왼쪽 카드, 오른쪽 카드, 양쪽 카드를 버리를 행동을 할 수 있다. 오른쪽 카드를 버릴때만 조건이 있고, 점수를 얻을 수 있어서 모든 카드쌍에 대한 경우의 수를 탐색하지는 않을 것이다.

그래도, 각 카드가 최대 2000개씩이므로, DFS와 DP두가지 방법을 고민했다. 깊어야 4000번 들어가고, 더 깊게 탐색하지 않을 것 같은 DFS와, 2000^2가지 경우의 수를 따로 탐색, 저장하는 DP를 고민하던 도중 일반적으로 DP가 더 빠른 경우가 많아 DP로 시도하였는데, 잘못 생각했던게 아닌가 싶다.

 

 

2. 풀이 코드

🖥Python(DP) - 4988ms

import sys
input = sys.stdin.readline
MIIS = lambda: map(int, input().split())


n = int(input())
left = list(MIIS())
right = list(MIIS())

# 왼쪽 i번째 카드, 오른쪽 j번째 카드일 때 점수
dp = [[-1] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(n):
        if dp[i][j] == -1:
            dp[i][j + 1] = -1
            continue
        # 1. 왼쪽 카드만 버리는 경우
        # 2. 두 카드 모두 버리는 경우
        # 3. 오른쪽 카드만 버려서 점수 얻는 경우
        if dp[i + 1][j] < dp[i][j]:
            dp[i + 1][j] = dp[i][j]
        if dp[i + 1][j + 1] < dp[i][j]:
            dp[i + 1][j + 1] = dp[i][j]
        if right[j] < left[i] and dp[i][j + 1] < dp[i][j] + right[j]:
            dp[i][j + 1] = dp[i][j] + right[j]


# 최대 점수 비교
max_score = dp[n][n]
for i in range(n):
    if max_score < dp[n][i]:
        max_score = dp[n][i]
    if max_score < dp[i][n]:
        max_score = dp[i][n]
print(max_score)

🖥Python(DFS) - 1996ms

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
MIIS = lambda: map(int, input().split())


def dfs(i: int, j: int) -> int:
    # 왼쪽 i카드, 오른쪽 j카드
    # 한 쪽 카드를 모두 사용했을 때
    if i == n or j == n:
        return 0
    # 이미 해당 칸에 도달했을 때
    # 모든 칸에서 최댓값을 저장하며 진행했으므로, 해당 값 반환
    if scores[i][j] >= 0:
        return scores[i][j]
    # 오른쪽 카드를 버리며 점수를 먹을 수 있을 때
    if left[i] > right[j]:
        scores[i][j] = dfs(i, j + 1) + right[j]
    # 왼쪽 카드, 왼쪽 + 오른쪽 카드를 버릴 때 점수
    # 순서대로 버리면서 더 큰 점수가 되기도 해서 모두 비교해야 되지만,
    # 어찌되었던 scores배열에 최댓값만 저장하면 되므로 상관 ㄴㄴ
    else:
        s1, s2 = dfs(i + 1, j), dfs(i + 1, j + 1)
        if s1 >= s2:
            scores[i][j] = s1
        else:
            scores[i][j] = s2
    return scores[i][j]


n = int(input())
left = list(MIIS())
right = list(MIIS())
scores = [[-1] * n for _ in range(n)]

print(dfs(0, 0))

📕풀이 방법

두가지 코드의 흐름은 비슷하다.

왼쪽 카드만 버리거나 양쪽 카드를 버리는 작업은 항상 할 수 있고, 추가 점수는 없다.

오른쪽 카드의 수가 더 작을때만 오른쪽 카드만 버리고, 점수를 얻을 수 있다.

이러한 문제는 거의 전체 경우의 수를 확인해야 한다고 생각이 들었고, DP와 DFS방식이 떠올랐다. 정확하게 분석해보지는 않았지만, 한쪽 카드만 버리는 작업이 균등하게 이루어지지 않아서 완전탐색을 하게되는 DP보다, 가능한 가장 큰 점수를 내는 경우의 수만 탐색하는 DFS가 더욱 빨리 작동한 것 같다.

 

점수의 계산 방식은 같지만, 두 알고리즘의 구조상 DP는 큰 점수를 가장 뒷쪽으로 보내주는 방식으로, DFS는 해당 카드 조합에서 얻을 수 있는 최대 점수를 그 이전 조합으로 가져오는 방식으로 풀었다.

 

 

3. 생각 정리

파이썬은 DFS보다 BFS가 속도가 더 빠르다고 알려져 있고(재귀때문), 그리고 일반적으로 DFS문제보다 DP가 더욱 빠르게 작동했었기 때문에 DP로 먼저 접근했다. 위에서도 말했듯이 DP보다 DFS가 더욱 빠르게 작동했고, 문제마다 풀이 방법을 다르게 적용해야 한다고 느끼게 되는 계기였다.

또한, 하나의 문제를 다양한 방법으로 푸는 방법을 종종 시도하려 하지만, 그러한 방법을 찾기 힘든 문제도 많다. 이런 문제를 만나 다양한 방법으로 풀어보고, 어떤 알고리즘이 어떤 문제를 푸는 데 더욱 적합한지 알아가는 과정을 가지는게 성장하는 하나의 과정이 아닐까 생각한다.