[Python 문제 풀이] 프로그래머스 '정수 삼각형'

DP의 정석적인 유형

 

조건파악

- 삼각형의 높이는 최대 500

- 바로 아래 양쪽에 있는 두 개의 노드로만 누산될 수 있다.

접근

 깊이 우선 탐색을 고려한다면 그것은 전체탐색이나 다름 없다. 최대가 어떤 경우에 발생하는지 알 수 없기 때문이다. 최상단에서 누적되는 방향이 두가지 밖에 없다 하더라도 경우의 수가 너무 많아진다. 다행히 최대가 되는 경로까지는 기록하지 않아도 되니 수의 합에만 집중할 수 있다.

 DP의 기본 원리는 큰 문제를 작은 문제로 분해하여 작성하는 것이다. 노드 하나에 더해질 수 있는 인접 노드는 두 개 뿐인 것에 주목하자. 최종적으로 최대값이 만들어지기 위해서는 단지 두 개의 노드 중 하나를 선택하는 작은 문제에서도 최대값을 취해야 한다.

 작은 문제를 발견한 다음엔 이것들의 결과를 전파시키면 된다. 정수 삼각형에서는 최정상에서 출발할 수도 있고 맨 아래층에서 출발할 수도 있다. 각각 윗층 혹은 아랫층에 인접한 두 개의 노드 중 더 큰 값을 누적시켜 가면 된다.

의사코드

1. triangle의 각 줄을 순회
2. 각 줄의 각 원소에 더해질 수 있는 두 값 중 큰 값을 가져와 누적
3. 마지막으로 누적된 값들의 최대값을 반환

구현

def solution(triangle):
    acc = [0,0] # 더미 데이터
    for line in triangle :
        tmp = []
        for i in range(len(line)) :
        	#인덱스를 기준으로 하여 인접한 두 개 중 큰 값을 누적
            tmp.append(max(acc[i],acc[i+1]) + line[i])
        acc = [0] + tmp + [0] #양 끝의 노드에서 0과 비교하여 큰 값을 가져오기 위한 더미 데이터
    return max(acc)