[Programmers] 땅따먹기

땅따먹기

땅따먹기 를 클릭하면 바로 이동한다.

처음엔 차례대로 내려오면서 인덱스가 겹치지 않게 최댓값을 찾아가는 아주 단순한 방법을 생각했다..

물론 역시 아니였다!!! 매번 문제를 풀 때 마다 한 번 더 생각하지 않고 바로 푸는 경향이 있는데 고쳐야겠다..

land = [[7, 7, 60, 100], [50, 10, 5, 100], [4, 7, 2, 300], [10, 2, 5, 900]] 가 주어지면 60 + 100 + 7 + 900 이 정답이다.

land = [[7, 7, 60, 100], [50, 10, 5, 100], [4, 7, 2, 300]] 가 주어지면 100 + 10 + 300 이 정답이다.

이렇게 일부는 같지만 어떤 행이 더 추가 되느냐에 따라 답이 달라진다..

[Programmers] 가장 큰 정사각형 찾기 문제가 생각났다!! 차례대로 반복을 하면서 최댓값을 찾아내는 문제..

DP를 통해 해결 해야한다는 것은 알았지만 해결방법이 도무지 생각이 나질 않았다..

정답은 아주 간단했다!! 시야를 너무 좁게 보고 있었다.. 각 행 마다 이전 행의 겹치지 않는 인덱스 중 최댓값을 더해가면 됐다.

---

from copy import deepcopy


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

	return max(dp[len(dp) - 1])

다 풀고보면 아주 쉬운문제이다.. DP 관련 문제를 더 많이 풀어봐야겠다.