[BOJ][🟡5][백준#10835] 카드게임

문제 출처

BAEKJOON Online Judge #10835

문제

지훈이는 최근에 혼자 하는 카드게임을 즐겨하고 있다. 게임에 사용하는 각 카드에는 양의 정수 하나가 적혀있고 같은 숫자가 적힌 카드는 여러 장 있을 수 있다. 게임방법은 우선 짝수개의 카드를 무작위로 섞은 뒤 같은 개수의 두 더미로 나누어 하나는 왼쪽에 다른 하나는 오른쪽에 둔다. 그리고 빈 통을 하나 준비한다.  이제 각 더미의 제일 위에 있는 카드끼리 서로 비교하며 게임을 한다. 게임 규칙은 다음과 같다. 지금부터 왼쪽 더미의 제일 위 카드를 왼쪽 카드로, 오른쪽 더미의 제일 위 카드를 오른쪽 카드로 부르겠다.

언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다. (1)과 (2)의 규칙에 따라 게임을 진행하다가 어느 쪽 더미든 남은 카드가 없다면 게임이 끝나며 그때까지 얻은 점수의 합이 최종 점수가 된다. 

다음 예는 세 장 씩 두 더미의 카드를 가지고 게임을 시작하는 경우이다

카드 순서 왼쪽 더미 오른쪽 더미

1 3 2

2 2 4

3 5 1

이 경우, 우선 오른쪽 카드 2가 왼쪽 카드 3보다 작으므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 모두 버리거나, 규칙 (2)에 따라 오른쪽 카드만 버릴 수 있다. 만약 오른쪽 카드만 버리는 것으로 선택하면, 2만큼 점수를 얻고 오른쪽 카드 2는 버린다. 이제 오른쪽 더미의 제일 위 카드는 4이고 이는 왼쪽 카드 3보다 크므로 규칙 (1)에 따라 왼쪽 카드만 버리거나 왼쪽 카드와 오른쪽 카드를 둘 다 버릴 수 있다. 만약 둘 다 버리는 것으로 선택하면, 이제 왼쪽 카드는 2가 되고 오른쪽 카드는 1이 된다. 이 경우 다시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 왼쪽 카드만 버리는 것으로 선택하면 이제 왼쪽 카드는 5가 되고 오른쪽 카드는 1이 된다. 이 경우에도 역시 규칙 (1)과 (2)에 따라 세 가지 중 한가지를 선택할 수 있고, 그 중 오른쪽 카드만 버리는 것으로 선택하면 1만큼 점수를 얻고 오른쪽 카드 1은 버린다. 이제 오른쪽 더미에는 남은 카드가 없으므로 규칙 (3)에 따라 게임이 끝나며 최종 점수는 2+1=3이 된다. 두 더미의 카드가 주어졌을 때, 게임을 통해 얻을 수 있는 최종 점수의 최댓값을 출력하는 프로그램을 작성하시오. 위 예에서 최종 점수의 최댓값은 7이다.

입력

첫 줄에는 한 더미의 카드의 개수를 나타내는 자연수 N(1 ≤ N ≤ 2,000)이 주어진다. 다음 줄에는 왼쪽 더미의 카드에 적힌 정수 A(1 ≤ A ≤ 2,000)가 카드 순서대로 N개 주어진다. 그 다음 줄에는 오른쪽 더미의 카드에 적힌 정수 B(1 ≤ B ≤ 2,000)가 카드 순서대로 N개 주어진다. 각 더미에는 같은 숫자를 가진 카드가 두 개 이상 있을 수 있다.

출력

얻을 수 있는 최종 점수의 최댓값을 출력한다.

예제

예제 1

입력

3
3 2 5
2 4 1

출력

7

예제 2

입력

4
1 2 3 4
4 1 2 3

출력

6

My Sol A: 정순으로 풀기(실패)

import sys
input = sys.stdin.readline

N = int(input())
Ls = [0] + list(map(int, input().split()))
Rs = [0] + list(map(int, input().split()))
dp = [[0]*(N+1) for _ in range(N+1)]

for l in range(1, N+1):
    for r in range(1, N+1):
        if Rs[r] < Ls[l]:
            dp[l][r] = max(dp[l-1][r-1], dp[l-1][r], dp[l][r-1]+Rs[r])
        else:
            dp[l][r] = max(dp[l-1][r-1], dp[l-1][r])

print(dp[N][N])

DP를 사용하는 문제 같았다. 위에부터 카드의 순서를 각각 l과 r이라고 할 때 이를 각각 행열로 따져 2차원 배열로 값을 구하는 방식이었다.

분명히 테스트케이스도 그렇고, 논리적으로도 틀릴 게 없을 것 같았는데, 계속 틀렸다는 결과를 받았다.

도저히 풀리지 않아 많은 블로그들을 참고해보았는데, 모두 문제를 역순으로 접근해서 풀었다.

My Sol B: 역순으로 풀기

import sys
input = sys.stdin.readline

N = int(input())
Ls = list(map(int, input().split()))
Rs = list(map(int, input().split()))
dp = [[0]*(N+1) for _ in range(N+1)]

for l in range(N-1, -1, -1):
    for r in range(N-1, -1, -1):
        if Rs[r] < Ls[l]:
            dp[l][r] = max(dp[l+1][r+1], dp[l+1][r], dp[l][r+1]+Rs[r])
        else:
            dp[l][r] = max(dp[l+1][r+1], dp[l+1][r])

print(dp[0][0])

나 역시 방식을 바꾸어 역순으로만 접근해 풀었는데 바로 합격이었다.

결과

맞았습니다!!

모범답안

출처

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()

내 풀이보다 절반에 가깝게 연산속도가 빠른 풀이를 가져와 분석해보려 한다.

내가 쓴 메모이제이션 저장 2차원 배열 dp를 cache라는 이름으로 정의하였고, -1의 값을 담아 초기화했다. global로 cache를 함수 내에 넣지 않고, 인자로 넣었고, 똑같이 역순으로 문제를 풀어 cache[0][0]를 출력하는 방식이었다.

특이한 점은 dfs를 이용해 cache를 채우는 방식인데, for문을 사용하는 것과 거의 같은데도 dfs를 사용하는 점이 인상 깊었다. 위험하다고 생각되는 부분은 a[left] > b[right]인 경우 cache를 max로 따지지 않고 dfs 함수의 바로 b[right]를 더해버리는 방식인데, 이것이 연산 시간의 차이를 야기하는 가장 큰 요인인 것 같다.

그런데 이것이 어떻게 가능할까? 비교해야하는 다른 요소들은 무시해도 되는 것일까? 고려할 필요가 없었을까? 의문이 들었다.