프로그래머스에 있는 동적계획법(Dynamic Programming) 문제이다. 먼저 점화식을 세웠다. 왼쪽 카드와 오른쪽 카드가 있으므로 2차원 배열 dp를 선언했고 내가 세운 점화식은 아래와 같다.
# dp[i][j] : left에서 i번째 카드, right에서 j번째 카드
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]+right[j-1])dp[i-1][j-1]은 left, right 두 개의 카드를 모두 버리는 경우이고, dp[i-1][j]는 left 카드를 버리는 경우이다. 마지막으로 dp[i][j-1]+right[j-1]는 left카드가 right카드보다 큰 경우에만 해당하며 right카드를 버림으로써 점수를 얻는 경우이다.
def solution(left, right):
if max(left) > max(right):
return sum(right)
dp = [[0 for _ in range(len(right)+1)] for _ in range(len(left)+1)]
for i in range(1, len(left)+1):
for j in range(1, len(right)+1):
dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])
if left[i-1] > right[j-1]:
dp[i][j] = dp[i][j-1]+right[j-1]
return max(dp[-1])이렇게 코드를 구현했을 때, 한가지 테스트케이스에서 넘어가지 않았다.
solution([2, 1, 1], [3, 1, 1])인 경우였는데, 기존 코드로는 해결할 수 없는 문제였다.
검색해본 결과, 반복문을 이용해서 푸는 방법은 0번째부터 dp배열을 채우는 것이 아닌 reversed()를 사용해 (n-1)번째부터 역방향으로 dp배열을 채우면 된다고 한다. 잘 이해는 안되지만 코드는 아래와 같다.
def solution_ok(left, right):
if max(left) > max(right):
return sum(right)
dp = [[0 for _ in range(len(right)+1)] for _ in range(len(left)+1)]
for i in reversed(range(len(left))):
for j in reversed(range(len(right))):
if left[j] > right[i]:
dp[i][j] = dp[i+1][j] + right[i]
else:
dp[i][j] = max(dp[i+1][j+1], dp[i][j+1])
return dp[0][0]