(파이썬) 정수삼각형 - 동적계획법

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

 

동적계획법 치곤 풀이가 간단한 편이라
처음 동적계획법을 접하는 분들께 좋을 듯함. 

 

보통 동적계획법 문제는 
1. 전체를 부분으로 나누고, 
2. 부분의 해를 저장하고 
3. 부분의 해를 (중복 계산하지 않고, 저장된 것을 재활용) 합쳐서 
풀이를 완성하는 방식을 사용한다.

 

이 때 전체를 부분으로 나누는 부분이 가장 까다롭지만.. 
부분 해를 저장하고 재활용하는 부분도 은근히 까다로운 경우가 많다. ㅠ.,ㅠ

 

이 문제의 경우 문제에서 표가 주어지고, 그 활용도 쉬운 편이라
동적 계획법 치곤 쉽게 풀 수 있다. 

 

----------------------------------------------------------

 

표로 나타내 보면 다음과 같다.

	0	1	2	3	4
0	7	3	8	2	4
1		8	1	7	5
2			0	4	2
3				4	6
4					5

 

가장 위의 7을 다음 1열에 더하자. 

	0	1	2	3	4
0		3+7	8	2	4
1		8+7	1	7	5
2			0	4	2
3				4	6
4					5

 

1열을 2열에 더하자. 이 때 2가지 경로가 가능한 가운데 숫자(1)는 이전 경로에서 더 큰 숫자를 더 해주면 된다. 

	0	1	2	3	4
0		3+7	8+3+7	2	4
1		8+7	1+8+7	7	5
2			0+8+7	4	2
3				4	6
4					5

 

이렇게 4열가지 반복해준 뒤 가장 큰 숫자를 찾으면 된다. 

 

def solution(triangle):
    for level in range(1, len(triangle)):
        for index, _ in enumerate(triangle[level]):
            v1 = triangle[level - 1][index - 1] if (index > 0) else 0
            v2 = triangle[level - 1][index] if (index < len(triangle[level - 1])) else 0
            triangle[level][index] += max(v1, v2)
    return max(triangle[-1])


print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))

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


print(solution([[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]))