프로그래머스 땅따먹기 파이썬

1. dfs(x)

가능한 모든 경우의 수를 구하기 위해 dfs를 사용했다.

깊이가 깊어지면 런타임에러가 발생하게 된다. 

answer=0
def dfs(land,now_x,now_y,pre_y,tot):
    global answer
    
    if len(land)==now_x:
        answer=max(answer,tot)
    elif pre_y != now_y:
        for i in range(4):
            dfs(land,now_x+1,i,now_y,tot+land[now_x][now_y])
  
def solution(land):
    global answer
    for i in range(4):
        dfs(land,0,i,-1,0)
    return answer

 

2. i행에서 i-1행을 값 선택

i행의 각 값에 선택할 수 있는 i-1행의 값들중 가장 큰값을 더해준다.

 

def solution(land):
    for i in range(1,len(land)):
        for j in range(len(land[0])):
            land[i][j]+=max(land[i-1][:j]+land[i-1][j+1:])
    
    return max(land[len(land)-1])