[Python : 프로그래머스] 땅따먹기

문제

https://programmers.co.kr/learn/courses/30/lessons/12913

풀이

문제에 제시된 조건을 읽자마자 각 행을 내림차순으로 정렬해서
이전 행에서 가져온 최대값과 열이 같으면 바로 다음 값을 찾는 식으로 구현했다.

def solution(land):
    answer, preidx = 0, -1
    land = [sorted(list(enumerate(x)), key=lambda x: x[1], reverse=True) for x in land]
    for row in land:
        print(row)
        if row[0][0] == preidx : #가장 큰 값의 인덱스가 이전과 같을 경우
            answer += row[1][1]
            preidx = row[1][0]
        else :
            answer += row[0][1]
            preidx = row[0][0]
        print(preidx)
            
    return answer

결과는 제시된 예시만 통과하고 전체 테스트케이스 실패.
조금씩 바꿔가며 시도해봤지만 계속해서 틀리길레
문제를 잘못 이해한건가 싶어서 질문 게시판을 살펴봤다.

max값을 담는게 항상 최대가 되진 않습니다.
[[1, 1, 99, 100], [1, 1, 1, 99]] 같은 경우
99, 99를 선택한 경우인 198이 최대가 되어야 합니다.
주재형―2020.08.13 13:18

주재형님, 감사합니다. DP로 접근하는 문제였다.
DP로 접근하는 문제인걸 인지하고 나니까, 열의 크기가 4로 고정된 이유가 이해 된다.
최대값을 4가지로 분할하여 각각 더해보자.

def solution(land):
    for i in range(1, len(land)):
        land[i][0] = max(land[i][0]+land[i-1][1], land[i][0]+land[i-1][2], land[i][0]+land[i-1][3])
        land[i][1] = max(land[i][1]+land[i-1][0], land[i][1]+land[i-1][2], land[i][1]+land[i-1][3])
        land[i][2] = max(land[i][2]+land[i-1][0], land[i][2]+land[i-1][1], land[i][2]+land[i-1][3])
        land[i][3] = max(land[i][3]+land[i-1][0], land[i][3]+land[i-1][1], land[i][3]+land[i-1][2])
        
    return max(land[i])

자신과 다른 열에 있는 값들과의 합 중 최대값을 자신이 갖는다.
이 동작을 모든 행에 걸쳐서 반복시키면 4개의 최대값이 나온다.
4개의 값 중 최대값이 문제에서 요구하는 최대값이 된다.

1시간을 넘게 고민한 문제인데 문제를 풀고 나서야
DP문제중에서도 가장 쉬운 축에 속한다는 걸 깨닫는다. 큰 일 났다.