08/30 카드게임 BOJ 10835 파이썬

https://www.acmicpc.net/problem/10835

10835번: 카드게임

1. 풀이

다이나믹 프로그래밍 문제다.

규칙 1, 2, 3에 따라 채워가면 되는 문제로 bottom up 방식을 사용했다.

 

* 먼저 카드 개수가 N이라고 할 때 N*N을 만들고 뒤쪽에서 부터 채워간다.

* i 인덱스는 left의 카드번호 j 인덱스는 right 의 카드번호를 의미한다.

* left[i] > right[j] 인 경우에는 오른쪽 카드를 버리고 스코어에 버린 카드 번호의 값을 더할 수 있고 그외의 경우에는 없다.

 

아래는 파이썬 코드이다. (Bottom up 방식)

import sys
input= sys.stdin.readline
n = int(input())
left = list(map(int, input().split()))
right = list(map(int, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]

for i in range(n-1, -1, -1):
    for j in range(n-1, -1, -1):
        if right[j] < left[i]:
            dp[i][j] = max(dp[i][j+1] + right[j], dp[i+1][j], dp[i+1][j+1])
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])

print(dp[0][0])

top down 방식

N = int(input())
left =[0] +list(map(int, input().split()))
right= [0]+list(map(int, input().split()))

dp = [[0 for i in range(N+1)] for i in range(N+1)]

for row in range(1,N+1):
    for col in range(1,N+1):
        if right[col] < left[row]:
            dp[row][col] = max(dp[row][col-1] + right[col], dp[row-1][col], dp[row-1][col-1])
        else:
            dp[row][col] = max(dp[row-1][col], dp[row-1][col-1])

print(dp[N][N])