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

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

코딩테스트 연습 - 땅따먹기 | 프로그래머스

Copy-Driven-Development 도 학습에 효과가 있단 사실을 깨달았다.

 

2020/01/27 - [취준/프로그래머스] - [프로그래머스 Programmers][Python] 도둑질

불러오는 중입니다...

이 글에서처럼 처음 상태에 대한 각각의 DP 배열을 만들고 풀었다.

첫번째 땅 1,2,3,4를 밟은 상태를 각각 dp1,dp2,dp3,dp4라고 하자,

다음번 땅부터는 dp1(첫번째 땅으로 시작한 배열) = max(dp2,dp3,dp4) + 첫번째 땅 공식이 성립한다.

각 2,3,4도 똑같이 하면 된다.

 

그리고 dp1~dp4 의 마지막 값중 가장 큰 값이 정답.

 

def solution(land):
    dp1,dp2,dp3,dp4 = [[land[0][0]],[land[0][1]],[land[0][2]],[land[0][3]]]
    
    for i in range(1,len(land)):
        d = land[i]
        ldp1,ldp2,ldp3,ldp4 = dp1[-1],dp2[-1],dp3[-1],dp4[-1]
        dp1.append(max(ldp2,ldp3,ldp4)+d[0])
        dp2.append(max(ldp1,ldp3,ldp4)+d[1])
        dp3.append(max(ldp2,ldp1,ldp4)+d[2])
        dp4.append(max(ldp2,ldp3,ldp1)+d[3])
        
    return max(dp1[-1],dp2[-1],dp3[-1],dp4[-1])