프로그래머스 땅따먹기 코드 및 해설 (파이썬)

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

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

 

💡 Dynamic Programming으로 풀이했습니다. 

 

먼저 주어진 land과 같은 shape의 dp라는 리스트를 생성합니다. 이때 모든 값은 0으로 초기화합니다. 

dp의 두 번째 줄부터, 각 위치에 도달할 때까지의 최댓값을 dp에 저장합니다. 이때 연속해서 같은 열은 방문할 수 없게 해줍니다. 

cf. dp의 첫 번째 줄에선 아직까지 더해온 값이 없어 그대로 0이므로 고려하지 않아도 됩니다. 

dp의 마지막 줄에 다다를 때까지 이를 반복하고, 마지막 줄에 도달하면 while문을 종료합니다.

 

여기까지 실행하면 dp의 마지막 줄엔 land의 마지막 줄의 각 위치에 도달할 때까지의 최댓값이 저장되어 있습니다. 이 값들을 각각 land의 위치에 해당하는 값과 더해주면, 각 위치에서 가능한 최종적인 합의 최댓값을 구할 수 있습니다. 이 리스트의 최댓값을 반환하면 정답을 얻을 수 있습니다. 

 

프로그래머스 정수 삼각형과 사실상 같은 문제입니다. 

그림과 함께한 더 자세한 풀이는 정수 삼각형 풀이 포스팅을 참고해주세요. 

 

def solution(land):
    N = len(land)
    # land 같은 shape의 0으로 초기화된 list 
    dp = [[0]*4 for i in range(N)]
    depth = 1

    # dp를 각 위치에서 가능한 최댓값으로 채우기 
    while depth < N:
        for idx, val in enumerate(land[depth]):
            possible_idx = [i for i in [0,1,2,3] if i != idx]

            max_val = 0
            for i in possible_idx:
                val = dp[depth-1][i] + land[depth-1][i]
                if max_val < val:
                    max_val = val 

            dp[depth][idx] = max_val

        depth += 1

    # dp의 마지막 줄의 값들을 각각 해당하는 triangle의 값과 더해 최댓값을 반환 
    return max([a+b for a,b in zip(dp[-1], land[-1])])