[프로그래머스][level2] 땅따먹기

문제 링크

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

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

 

풀이 

- dp 문제 

1행은 다른 땅을 밟고 도착하지 않으므로 2행부터 시작 

2행부터 전 행에서 자기 자신과 같은 열을 제외한 다른 열의 최댓값 더하기 

 

계속 누적되어 마지막 행의 최댓값이 정답이 된다. 

def solution(land):
    n = len(land)
    
    for i in range(1, n):
        for j in range(4):
        	# i-1 행의 0열을 제외한 다른 열의 최댓값 더하기 
            if j == 0 :
                land[i][j] += max(land[i-1][1:])
            # i-1 행의 1열을 제외한 다른 열의 최댓값 더하기 
            if j == 1 :
                land[i][j] += max(max(land[i-1][2:]),land[i-1][0])
            # i-1 행의 2열을 제외한 다른 열의 최댓값 더하기 
            if j == 2 :
                land[i][j] += max(max(land[i-1][:2]),land[i-1][3])
            # i-1 행의 3열을 제외한 다른 열의 최댓값 더하기 
            if j == 3:
                land[i][j] += max(land[i-1][:-1])
                
    # 마지막 행의 최댓값 
    return max(land[-1])