[Python] 프로그래머스. 땅따먹기 (Level 2)

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

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

DP문제.

 

table[row][index] 위치가 row, index위치까지 도달했을 때 얻을 수 있는 최댓값이라고 정의한다면,

이 값은 land[row][index] + max(table[row-1][0~4까지의 값 중 index를 제외한 나머지]) 가 된다.

 

만약 row가 1이고 index가 2라면

table[1][2] = land[1][2] + max(table[0][0], table[0][1], table[0][3])이 되는 것.

 

table을 따로 생성할 수도 있지만,

land[row][index] = land[row][index] + max(land[row-1][range(4) - {index}] 그대로 연산해도 무방하다.

 

 

	def solution(land):
	for row in range(1, len(land)):
	# 밟을 칸(index) 선택
	for i in range(4):
	# 밟은 칸 제외한 나머지 칸
	rest = set(range(4)) - {i}
	# 밟은 칸 제외한 나머지 칸들의 최댓값을 다음 row의 index에 저장.
	land[row][i] += max([land[row-1][index] for index in rest])
	# 마지막 row에서 얻을 수 있는 점수의 최댓값을 확인한다.
	return max(land[-1])

view raw [프로그래머스] 땅따먹기.py hosted with ❤ by GitHub