[프로그래머스 LV 2 ] 땅따먹기 파이썬/python

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

코딩테스트 연습 - 땅따먹기

 

파이썬 이차원 메모이제이션 초기화 [-1,-1,-1,-1] * 100001  로 하면안됨!!!!

dp = [[-1] * 4 for _ in range(100001)] 이걸로 해줘야함!!!!!

 

재귀깊이가 1,000 으로 고정되어있어서 

sys.setrecursionlimit(1000001)

이거 적어줬음!! 

앞으로 파이썬으로 재귀 풀떄 바텀업만 풀어야되나; 저거땜에 시간을 얼마를 날려먹은건지;

 

 

 

코드!

import sys
 
sys.setrecursionlimit(1000001)
 
dp = [[-1] * 4 for _ in range(100001)]
 
 
# dp[x] == 현재 x를 밟고있을때 아래로 내려갈경우 얻는 가장 큰 값
def max_sum(x, y, land):
    if x == len(land) - 1:
        return land[x][y]
 
    if dp[x][y] != -1:
        return dp[x][y]
 
    for i in range(4):
        if i != y:
            s = land[x][y] + max_sum(x + 1, i, land)
            dp[x][y] = max(dp[x][y], s)
 
    return dp[x][y]
 
 
def solution(land):
    answer = 0
    for i in range(4):
        answer = max(answer, max_sum(0, i, land))
 
    return answer