프로그래머스 43105 정수 삼각형 파이썬 풀이

난이도 : Lv. 3

풀이일 : 2411052

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

프로그래머스

---

문제

---

풀이 코드

def solution(triangle):
    dp = [[0] * len(triangle[-1]) for _ in range(len(triangle[-1]))]
    dp[0][0] = triangle[0][0]
    
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])  + triangle[i][j]
    
    answer = max(dp[-1])
    return answer

• dp : 현재까지의 최대 숫자의 합을 담을 배열
• dp[0][0]에는 최초 시작 숫자를 담아준다.
• for 반복문은 삼각형 제일 위 꼭지점의 아래줄 부터 시작하고, j는 i줄에 있는 숫자 만큼 반복한다.
• 각 자리에 한 칸 위 오른쪽, 한 칸 위 왼쪽 숫자와 현재를 더한 값 중 큰 것을 저장한다.
• 마지막 줄에서 가장 큰 값을 answer에 할당한다

---

느낀점

• 맨날 잘 못하는 dp 모아서 연습해야지
• dp를 보통 dp로 잘 인식하지 못하는 것 같아서 유형별로 좀 적응하는 시간이 필요할 것 같다.