[programmers] 프로그래머스 정수 삼각형(Python)

(주)그렙

[programmers] 프로그래머스 정수 삼각형

(Python)

(글쓴날 : 2020.06.07)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 정수 삼각형

---

1) 문제

문제 링크 :https://programmers.co.kr/learn/courses/30/lessons/43105 

코딩테스트 연습 - 정수 삼각형

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

삼각형 형태의 2차원 정수 배열이 주어질 때, 꼭대기에서 바닥까지 특정 규칙에 의해 내려가며 합한 수 중 가장 큰 수를 구하는 문제입니다.

 

저의 경우, 동적 계획법을 적용하였고, Python을 사용했습니다.

memoizaion을 위해 따로 테이블을 마련하지 않고, 규칙에 만족하는 합한 값을 기존 배열에 덮어씌워가며 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == len(triangle[i]) - 1:
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
                
    return max(triangle[-1])

---