프로그래머스 python 정수 삼각형

[level 3] 정수 삼각형 - 43105

문제 링크

성능 요약

메모리: 17.6 MB, 시간: 63.11 ms

구분

코딩테스트 연습 > 동적계획법（Dynamic Programming）

채점결과

정확성: 64.3
효율성: 35.7
합계: 100.0 / 100.0

제출 일자

2025년 04월 23일 22:51:34

문제 설명

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

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

제한사항

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

입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

코드

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

이 문제는 dp를 이용해야 할 것 같았다.

그래서 점화식을 구하기 위해 하나씩 대입해보며 값을 구했다.

아래는 점화식을 구하기 위한 방법이다.

cnt[0][0] = triangle[0][0]
cnt[1][0] = cnt[0][0] + triangle[1][0]
cnt[1][1] = cnt[0][0] + triangle[1][1]
cnt[2][0] = cnt[1][0] + triangle[1][0]
cnt[2][1] = max(cnt[1][0] + triangle[2][1], cnt[1][1] + triangle[2][1])
cnt[2][2] = cnt[1][1] + triangle[2][2]

첫 인덱스, 마지막 인덱스, 이외의 인덱스들은 서로 점화식이 다르다.

확인해보면 첫 인덱스는 `cnt[t][i] = cnt[t-1][i] + triangle[t][i]`이러한 점화식이 나오게 된다.

이외의 인덱스들은 바로 옆의 값들 중 최댓값을 구해야 한다.