Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

10835. 카드게임

(골드 V) 두 개의 카드더미로 하는 게임에서 얻을 수 있는 최대 점수를 동적 프로그래밍과 DFS를 이용하여 풀이하였다.

문제 링크

문제 요약

$2N$ 개의 카드가 주어졌다. 각 카드에는 양의 정수가 하나 적혀있고, 좌・우로 $N$개씩 두 개의 더미로 나누어 카드게임을 진행한다. 각 턴에는 아래의 행동 중 하나를 할 수 있다.

  • 왼쪽 카드만 버린다.
  • 양쪽 카드 모두 버린다.
  • *오른쪽 카드만 버린다. (오른쪽 카드의 숫자가 왼쪽보다 커야한다. 오른쪽 카드에 적힌 수를 점수로 얻는다.)

두 카드 더미 중 하나라도 빈다면 게임이 끝난다. 게임을 통해 얻을 수 있는 최대 점수를 구해야 한다.

Brute Force 이용한 풀이. (31점)

처음 문제를 보자마자 든 생각은 “그리디인가…? 아니면, 모든 케이스에 대해 시뮬레이션 해봐야 하나?” 였다. 그 생각을 함과 동시에 바로, Queue를 이용한 Brute Force무차별 대입 풀이를 먼저 시도하였다.

아래의 코드를 보면 Queue큐와 반복문을 이용한 방식으로 모든 케이스를 시뮬레이션 한다. 매 단계마다 카드 덱을 통채로 큐에 넣으면 시・공간적으로 매우 비효율적일 것이기에, 큐에는 좌우 카드 더미에서 다음에 뽑을 카드의 위치 두 곳과, 현재까지 누적된 점수만을 담았다.

from collections import deque
from collections import namedtuple
from typing import Deque


Node = namedtuple('Node', ['left', 'right', 'score'])

LEFT_DECK = []
RIGHT_DECK = []


def left_card(index: int) -> int:
    return LEFT_DECK[index]

def right_card(index: int) -> int:
    return RIGHT_DECK[index]

def pop_left(q: Deque, node: Node) -> None:
    n = Node(node.left+1, node.right, node.score)
    q.append(n)

def pop_both(q: Deque, node: Node) -> None:
    n = Node(node.left+1, node.right+1, node.score)
    q.append(n)

def pop_right(q: Deque, node: Node) -> None:
    if right_card(node.right) < left_card(node.left):
        n = Node(node.left, node.right+1, node.score+right_card(node.right))
        q.append(n)


if __name__ == "__main__":
    N = int(input())
    LEFT_DECK.extend(map(int, input().split()))
    RIGHT_DECK.extend(map(int, input().split()))

    max_score = 0

    q: Deque[Node] = deque()
    q.append(Node(0,0,0))

    while q:
        node = q.popleft()
        if N <= node.left or N <= node.right:
            max_score = max(max_score, node.score)
        else:
            pop_left(q, node)
            pop_both(q, node)
            pop_right(q, node)

    print(max_score)

이 풀이로는 좋은 시간효율을 기대하지 못한다는 것을 알고 있었지만, 생각보다 더 낮은 점수인 31/100점을 받았다.

31점을 획득했다는 것은, $1 \leq N \leq 10$ 에서는 이 풀이가 유효하나, $10 \leq N \leq 25$ 에서는 유효하지 않다는 것이다.

시간 복잡도

걸릴 시간을 대충 추정해보자. 빅-오 표기법에서, $O(N)$ 일 때, $N = 100,000,000$ 이면 1초로 보면 된다는… 그런 느낌이 있다.

이 문제를 BF로 풀이할 경우, 매 순간 2~3개의 선택지가 있다고 생각해볼 수 있다. 그러면 대강 $O(3^N)$ 정도의 복잡도를 가지지 않을까? 그러할 경우 $N = 17$ 만 되어도 $3^N = 129,140,163$ 으로 시간 제한을 맞추기엔 어림도 없어진다. 하물며 문제의 조건에 따르면 최악의 경우 $1 \leq N \leq 2,000$ 이니, 절대 다른 알고리즘을 찾아야 한다.

$N = 2,000$ 이라고 볼 때, 허용 가능 한 것은 $O(N^2)$ 정도라고 생각하면 될 것 같다.

Dynamic Programming & DFS - Python 3 (64점)

다음으로는 동적 프로그래밍을 통해 접근해보기로 했다. 앞서 BF로 풀이한 것과 동일한 것은, 각 카드 더미에서 뽑은 카드의 개수로 현 상태를 구분한다는 것이다. 그러나 이번에는 메모이제이션을 통해 방문체크를 할 수 있게 되어, 중복된 계산은 지양할 수 있게 된다. 최대 $N \times N$ 회만 계산하면 되므로 시간복잡도 $O(N^2)$로 안정적이게 풀 수 있을 것으로 예상하였다.

import sys
sys.setrecursionlimit(int(1e6))


N = int(input())

LEFT_DECK = list(map(int, input().split()))
RIGHT_DECK = list(map(int, input().split()))


# dp[i][j] 왼쪽 카드를 i개, 오른쪽 카드를 j개 버렸을 때 얻을 수 있는 최대 점수 메모이제이션
dp = [[-1] * (N+1) for j in range((N+1))]


def simulate(left: int, right: int) -> int:
    if N <= left or N <= right:
        dp[left][right] = 0

    if dp[left][right] == -1:
        dp[left][right] = max(dp[left][right], simulate(left+1, right))
        dp[left][right] = max(dp[left][right], simulate(left+1, right+1))

        if LEFT_DECK[left] > RIGHT_DECK[right]:
            dp[left][right] = max(dp[left][right], simulate(left, right+1)+RIGHT_DECK[right])

    return dp[left][right]


print(simulate(0, 0))

이 풀이를 통해 $0 \leq N \leq 25$ 의 케이스는 가뿐히 통과해 64점까지 득점하였다.

하지만 역시, Python은 타언어에 비해 태생적으로 매우 느리다는 한계가 있다. Python3으로 제출 시 $0 \leq N \leq 2000$ 에서 시간 초과를 받았으며, PyPy3으로 제출시에는 메모리 초과를 받았다.

Dynamic Programming & DFS - Java 8 (100점)

그래서 현재 어느정도 배워가는 중인 자바로 최대한 코드를 옮겨보았다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;


public class Main {
    static int n;
    static int[][] dp;
    static Stack<Integer> left_deck, right_deck;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        left_deck = new Stack<Integer>();
        right_deck = new Stack<Integer>();

        n = Integer.parseInt(stringTokenizer.nextToken());

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < n; i++)
            left_deck.push(Integer.parseInt(stringTokenizer.nextToken()));

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < n; i++)
            right_deck.push(Integer.parseInt(stringTokenizer.nextToken()));

        System.out.println(Integer.toString(solve()));

        bufferedReader.close();
    }

    public static int solve() {
        dp = new int[2001][2001];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                dp[i][j] = -1;

        return _solve(0, 0);
    }

    private static int _solve(int i, int j) {
        if (i >= n || j >= n)
            dp[i][j] = 0;

        if (dp[i][j] == -1) // If not visited
        {
            dp[i][j] = Math.max(dp[i][j], _solve(i + 1, j));
            dp[i][j] = Math.max(dp[i][j], _solve(i + 1, j + 1));

            if (left_deck.get(i) > right_deck.get(j))
                dp[i][j] = Math.max(dp[i][j], _solve(i, j + 1) + right_deck.get(j));
        }

        return dp[i][j];
    }
}

느낀 점

Python 3 의 구현속도는 경이로울 정도로 빠르나, 성능은 그러하지 못하다. 이대로 PS를 계속 해나아가려면 Python으로 빠르게 알고리즘을 검증하고 다른 언어로 옮길 수 있거나, 혹은 아예 다른 언어를 숙달해둘 필요성이 있다고 느꼈다.

Back to top