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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

코드를 작성하기 위한 순서는 다음과 같다.

1. 위에서 아래로 내려오면서 가장 큰 합을 구해야하기 때문에 DP를 사용한다.

2. 연속적으로 동일한 열은 구할 수 없기 때문에 같은 열은 제외하여 더해준다.

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

초기 코드를 작성할 때는 DP를 사용하지 않았다.

각 열마다 가장 큰 숫자를 구하고 만약 가장 큰 숫자가 연속된 열일 경우, 해당 숫자를 -1로 바꾸고 두번째로 큰 숫자를 구해주었다.

하지만 첫번째 행에서 최댓값을 더해준다고 전체 합이 최대가 되지는 않기 때문에 적절하지 않은 방법이었다.

따라서 순서대로 값을 더해주는 DP 방법을 사용하여 문제를 해결할 수 있었다.

합의 최댓값이나 최솟값을 구하는 문제는 DP를 우선적으로 사용하여야할 듯하다.