[프로그래머스💯] 코딩테스트 연습 > 동적 계획법 > 카드 게임

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

import sys
sys.setrecursionlimit(10**6)

global cached
cached = [[-1 for _ in range(2000)] for _ in range(2000)]


def dump(l, r, L, R, lA, rA):
    global cached
    if l == L or r == R:
        return 0
    if cached[l][r] != -1:
        return cached[l][r]
    if rA[r] < lA[l]:
        cached[l][r] = max(dump(l+1, r, L, R, lA, rA),
    	dump(l+1, r+1, L, R, lA, rA), (dump(l, r+1, L, R, lA, rA) + rA[r]))
    else:
        cached[l][r] = max(dump(l+1, r, L, R, lA, rA),
        dump(l+1, r+1, L, R, lA, rA))
    return cached[l][r]


def solution(left, right):
    global cached
    L_MaxIndex = len(left)
    R_MaxIndex = len(right)
    return dump(0, 0, L_MaxIndex, R_MaxIndex, left, right)

 

풀이)

재귀함수를 이용해 모든경우를 완전탐색했다.

 

2가지 경우로 나눠,

- 오른쪽 카드가 왼쪽보다 작은경우 : 왼쪽카드 하나버리기, 둘다 버리기, 오른쪽 카드 하나버리고 오른쪽 카드값 더하기

- 오른쪽 카드가 왼쪽보다 크거나 같은 경우 : 왼쪽카드 하나버리기, 둘다 버리기

 

함수의 각각의 경우에 최적해가 정해져있기 때문에 동적계획법을 쉽게 적용할 수 있다.

 

예를들어 문제 케이스 [3,2,5], [2,4,5] 를 생각해보자.

함수의 재귀가 진행되다가 왼쪽 인덱스 1, 오른쪽 인덱스 1 인 경우에 도달했다. (인덱스는 0 부터 시작)

현재 왼쪽카드 인덱스 1 , 오른쪽카드 인덱스 1 인경우 : [2,5], [4,1] 의 최적해는 이 전에 했던 점수랑 상관없이 1로 항상 일정하다. 그러므로 그 해는  cached 배열에 저장해 둔 후 다른 계산 없이 바로 이용할 수 있다.

 

 

 

(문제를 제데로 안읽어서, L_MaxIndex 와 R_MaxIndex 를 굳이 둘다 구했는데 문제에서 오른쪽카드와 왼쪽 카드의 수는 같다고 했기에 둘중에 하나는 없애도 된다..)

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges