문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land							answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

접근 방법

이번 문제를 처음 봤을 때에는 DFS를 통해 해결하려고 하였다. 그러나 시간초과가 발생하였고, 다이나믹 프로그래밍을 통해 해결해야 한다는 것을 알게 되었다. 이 문제의 점화식은 다음과 같이 구할 수 있었다.
DP[i][j]=max(DP[i-1])+land[i][j]
그러나 이 점화식만 사용한다면 같은 열에 접근하는 경우가 생기므로 예외 처리를 해야한다.
예외 처리를 위해 두번째로 작은 수의 x좌표를 반환하는 함수를 따로 작성하였고, 만약 max(DP[i-1])의 x좌표가 현재의 x좌표와 같을 경우에 작성한 함수를 사용하여 다른 x좌표를 취하도록 하였다. 이 경우의 점화식은 다음과 같다.
DP[i][j]=dp[i-1][get_second(i-1)]+land[i][j]
이 점화식을 사용하여 문제를 잘 해결하였다.

• 두번째로 큰 수의 x좌표를 반환하는 함수 get_second를 y를 인자로 갖도록 선언한다.
  -> land[0]의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  --> 만약 dp[y][i]가 내림차순으로 정렬된 dp[y][1]과 같을 경우, i를 반환한다.
• dp를 0으로 land의 길이*land[0]의 길이만큼 채워 선언한다.
• land[0]의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  -> dp[0][i]를 land[0][i]로 갱신한다.
• 1부터 land의 길이까지 반복하는 i에 대한 for문을 돌린다.
  -> 임시변수 idx에 dp[i-1]의 최댓값의 x좌표를 저장한다.
  -> land[0]의 길이만큼 반복하는 j에 대한 for문을 돌린다.
  --> 만약 idx가 j와 같을 경우,
  ---> dp[i][j]를 dp[i-1][get_second(i-1)]+land[i][j]로 갱신한다.
  --> 그 외에는 dp[i][j]를 max(dp[i-1])+land[i][j]로 갱신한다.
• max(dp[len(land)-1]을 반환한다.

solution.py

def solution(land):
    def get_second(y):
        for i in range(len(land[0])):
            if dp[y][i]==sorted(dp[y], reverse=True)[1]:
                return i
    dp=[[0]*len(land[0]) for _ in range(len(land))]
    for i in range(len(land[0])):
        dp[0][i]=land[0][i]
    for i in range(1, len(land)):
        idx=dp[i-1].index(max(dp[i-1]))
        for j in range(len(land[0])):
            if idx==j:
                dp[i][j]=dp[i-1][get_second(i-1)]+land[i][j]
            else:
                dp[i][j]=max(dp[i-1])+land[i][j]
    return max(dp[len(land)-1])