[프로그래머스💯] 코딩테스트 연습 > 동적 계획법 > 정수 삼각형 / Python 문제풀이

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

 

def solution(triangle):
    answer = 0
    length = len(triangle)
    #  length+1 한 이유 : 맨밑줄 index 넘어가도 오류안나게
    maxPath = [[0 for _ in range(length+1)] for _ in range(length+1)]
    maxPath[0][0] = triangle[0][0]
    for i in range(length-1):
        for j in range(i+1):
            # 왼쪽 밑 보고 갱신
            if maxPath[i][j] + triangle[i+1][j] > maxPath[i+1][j]:
                maxPath[i+1][j] = maxPath[i][j] + triangle[i+1][j]
            # 오른쪽 밑 보고 갱신
            if maxPath[i][j] + triangle[i+1][j+1] > maxPath[i+1][j+1]:
                maxPath[i+1][j+1] = maxPath[i][j] + triangle[i+1][j+1]
    return max(maxPath[length-1])

 

 

풀이)

동적 계획법의 대표적인 문제이다.

1. 삼각형 배열이랑 똑같은 복사본 이차원 배열을 만들어놓는다.

2. 그 배열에 현재까지 거쳐간 경로중 최대값만을 저장해놓는다. (최적해)

3. 그러면 그 밑줄은 그 최대값을 이용해 바로 구할 수 있다.

 

즉, 계속해서 한줄씩 최적해를 구해나가면,

처음부터 계산할 필요 없이 바로 윗줄의 최적해를 이용해서 계산할 수 있다.

 

 

 

* 이 문제 및 로고의 저작권은 Programmers에 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges