[DP][lv.3] 정수 삼각형 - 파이썬(Python)

https://school.programmers.co.kr/learn/courses/30/lessons/43105

 

 

문제

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

 

---

 

💡 사고과정

 

 

💻 내가 쓴 정답코드

사고한걸 바로 코드로 작성해서, 바로 정답이 나오니까 너무 좋다 ㅎㅎ

def solution(triangle):

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

 

 

 

 

 

 

 

🧐 추가학습 : deepcopy

import copy

def solution():
    
    #01 - 얕은 복사 (shallowCopy) : <객체의 주소> 복사
    triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
    dp = triangle 
    dp[0][0] = 1 #변경
    print(dp[0], triangle[0]) #함께 변경됨 (같은주소)
    
    
    #02 - 깊은 복사 (deepCopy) : 깊은 복사는 전체 복사로 <참조된 객체 자체>를 복사
    triangle = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
    dp = copy.deepcopy(triangle)  
    dp[0][0]= 1 #변경
    print(dp[0], triangle[0]) #함께 변경되지 않음 (다른주소)