Lv3. 정수 삼각형

문제 보기 :  정수 삼각형

프로그래머스

---

문제

• 정답률 : 60%

 

 

 

---

작성 코드

def solution(triangle):
    answer = triangle[0][0]
    l = len(triangle)
    dp = [0] * l
    dp[0] = triangle[0] #[[7],0,0,0,0]
    for i in range(1,l):
        dp[i] = [0] * (i+1) #[[7],[0,0],[0,0,0],[0,0,0,0],[0,0,0,0,0]]
        for j in range(i+1):
            if j==0:
                dp[i][j] = dp[i-1][j] + triangle[i][j] #18+2
            elif j==i:
                dp[i][j] = dp[i-1][j-1] + triangle[i][j] #15+4
            else:
                dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]
    answer = max(dp[l-1])
    return answer #[[7],[10,15],[18,16,15],[20,25,20,19],[24,30,27,26,24]]

---

풀이

문제를 풀기 전에 평소대로 규칙을 먼저 찾았는데, 위에서 아래로 내려가면서 정답을 찾는 것보다는 아래에서 위로 올라가는 방법이
코드도 짧고 차지하는 메모리도 적을 거라 생각했는데 테스트 케이스에서 자꾸 걸리는 문제가 발생했다

그래서 문제에 동적계획법이라고 써있는 태그대로 해보기로 했고 위에서 아래로 진행하는 코드를 쓰는건 너무 복잡해서 다른 예시들을 참고했다.

(이렇게 쓰면 메모리 초과가 뜰 줄 알았는데 아니었다..)

---

문제 해설)

1. dp라는 문제 풀이에 이용할 리스트 생성
2. dp 내부에는 triangle 내 리스트들과 길이가 같은 리스트를 입력
3. dp 내 첫번째 리스트는 triangle[0]으로 두고, 두번째 리스트부터는 앞 리스트 원소들과 triangle[1]의 j번째 원소를 추가한다.
4. 세번째 리스트부터는 양쪽 사이드 원소를 제외하고 나머지 원소는 앞 리스트의 같은 자리 원소 + 더해야하는 triangle[i][j]를 더한 값이 가장 큰 값으로 입력한다.