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

문제

프로그래머스 - 땅따먹기

해결 과정

• DP를 이용한 풀이
• 가장 바깥 for문: 1행부터 마지막 행까지 확인
• 가장 안쪽 for문: 행의 원소의 갯수만큼 확인
  • 이전 행에 있던 같은 열의 요소는 제외하고 가장 큰 요소들을 더하면서 진행
  • ex) 1행 0열 = 원래의 1행 0열 + (0행 0열을 제외한 0행의 값 중에서 가장 큰 값)
  • 1행 1열 = 원래의 1행 1열 + (0행 1열을 제외한 0행의 값 중에서 가장 큰 값)
  • ... 2행 2열 = 원래의 2행 2열 + (1행 2열을 제외한 1행의 값 중에서 가장 큰 값)

시행착오

• 이게 DP라고?

풀이

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[-1])