[프로그래머스 Programmers][Python] 카드 게임 (3/13 수정)

문제 : https://programmers.co.kr/learn/courses/30/lessons/42896

프로그래머스

(3/13 이후 테스트케이스가 추가되었습니다. 따라서 기존 풀이로는 풀리지 않습니다.)

 

DP 단골 문제 길찾기에서 방향만 하나 더해지는 거니까 어렵지 않게 풀 수 있다. 어려웠다.

 

댓글에서 알려주신 [2,1,1], [3,1,1] 예시를 들면

예전 코드에서는 2가 나온다.

그런데 2가 나올려면 (2,3) 상황에서 오른쪽의 3을 버려야 각각 1,1 을 버릴 수 있게 되어 2가 나온다.

근데 이건 불가능하다. 이런 불가능한 상황을 체크해야 하는데 저번 풀이에서는 그런 상황에 대한 체크가 없었다.

 

기존 방법 정방향 DP 배열	2	1	1
3	0	0	0
1	1 (2,3 상황에서 3을 버려야함)	1	1
1	2	2	2

 

도저히 모르겠어서 프로그래머스 질문을 봤는데, 반복문을 이용해서 푸는 방법은 0번째 부터 DP 배열을 채우는게 아닌, N-1번째 부터 역방향으로 채우면 된다고 한다.

역방향 DP 배열	2	1	1
3	0(밑에 2를 가져올 수는 없다)	0	0
1	2	0	0
1	1	0	0

 

잘 모르겠다. DP 는 언제봐도 어려운것 같다.

def solution_new(left, right):

    arr = [[0 for _ in range(len(left)+1)] for _ in range(len(right)+1)]

    for i in reversed(range(len(right))):
        for j in reversed(range(len(left))):
            if left[j] > right[i]:
                arr[i][j] = arr[i+1][j] + right[i]
            else:
                arr[i][j] = max(arr[i+1][j+1], arr[i][j+1])


    return arr[0][0]

현재 위치 i,j 에서 i = 오른쪽, j= 왼쪽이니까, left[j]>right[i] 일 때만 right[i]를 더하고 넘어갈 수 있다.

따라서, arr[i+1][j] 즉, 오른쪽 카드를 버리면서 넘어갈려면 현재 i,j 에서의 조건을 확인해야 한다.

 

뭐 이렇게 이해해야 되나 싶다.

 

 

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

10835번: 카드게임

이 문제랑 같은 문제인것 같다.

 

 

=================(기존 풀이)=================

 

 

DP 문제다.

길찾기 문제와 별 다를 바 없지만, 조건 하나가 들어간다.

왼쪽 카드가 오른쪽 카드보다 클 때만 카드값이 더해진다는 것이다.

다른 경우 (L==R, L<=R)는 그냥 갈 수 있다.

DP 단골 문제 길찾기에서 방향만 하나 더해지는 거니까 어렵지 않게 풀 수 있다.

 

 

i, j를 각각 오른쪽, 왼쪽 의 첨자라 하자

1. 각 위치에서 왼쪽 카드 > 오른쪽 카드 일 경우:
   1. arr[i][j] = arr[i-1][j] + right[i] 오른쪽 카드 움직이니까 한 장 전 값+ 현재 오른쪽 카드값
2. 각 위치에서 왼쪽 카드 <= 오른쪽 카드 일 경우:
   
   1. 둘 다 버리는 경우 or 왼쪽만 버리는 경우중 큰 값
   2. arr[i][j] = max(arr[i-1][j-1],arr[i][j-1])
3.  arr[len(right)-1][len(left)-1] 이 답이 된다.

def solution(left, right):
    
    arr = [[0 for _ in range(len(left)+1)] for _ in range(len(right)+1)]

    for i in range(len(right)):
        for j in range(len(left)):
            if left[j] > right[i]:
                arr[i][j] = arr[i-1][j] +  right[i]
            else:
                arr[i][j] = max(arr[i-1][j-1],arr[i][j-1])

    return arr[len(right)-1][len(left)-1]