[프로그래머스💯] 코딩테스트 연습 > 동적 계획법 > 정수삼각형🔺

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

<출처 : 프로그래머스(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. 입력 삼각형과 같은 크기의 배열 maxPath를 만들어 0으로 초기화한다.

(maxPath배열에는 현재까지 올 수 있는 경로의 최대 값이 담길것이다.)

2. 삼각형을 순차적으로 돌며 (오른쪽 아래, 혹은 왼쪽 아래 의 값이 더 커질 수 있으면 maxPath를 갱신해준다.)

3. 제일 아랫줄 숫자중 가장 큰 값을 출력한다.

 

 

 

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