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

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

프로그래머스

 

 

1. 해결방법

이번 문제의 해결 알고리즘은 DP이다.
DP 공부를 거의 안하다 보니 시간이 엄청 오래 걸렸다. 많이 풀다보면 느낌이 올만한 문제였을 것 같다.

열의 길이는 4로 제한되어있으니 작업중인 행과 이전의 행, 열의 인덱스의 값을 비교해서 작업중인 행, 열의 인덱스 값에 추가해주도록 하는 방식으로 구현하면 된다.

다만 연속적으로 같은 열의 인덱스를 선택할 수 없으므로 작업중인 행 이전의 행에 해당하는 열 인덱스를 0으로 초기화 한다. 물론 로직이 끝났으면 다음 for문에 영향 안가게끔 원상태로 값을 돌려놔야 한다.

 

 

2. 정답코드

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