취준/프로그래머스
[프로그래머스 Programmers][Python] 땅따먹기
puff
2020. 1. 29. 16:17
문제 : https://programmers.co.kr/learn/courses/30/lessons/12913
코딩테스트 연습 - 땅따먹기 | 프로그래머스
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면
programmers.co.kr
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])