정수 삼각형

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

프로그래머스

문제요약:

삼각형이 있을때 바로위 왼쪽 오른쪽중 큰것을 선택해서 내려올 수 있다. 맨아래층중 가장 큰 수를 구하시오.

 

소요시간:

5분

난이도3(2나 1로 조정 필요한듯)

 

코딩:

def solution(triangle):
	#맨위줄은 건너뛴다
	for i in range(1,len(triangle)):
		for j in range(i+1):
			#맨 왼쪽줄
			if j == 0:
				triangle[i][j]+=triangle[i-1][j]
			#맨 오른쪽줄
			elif j == i:
				triangle[i][j]+=triangle[i-1][j-1]
			#가운데
			else:
				triangle[i][j]+=max(triangle[i-1][j],triangle[i-1][j-1])
	return max(triangle[-1])

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

가장 전형적인 DP문제 입니다. 위에서부터 내려오며 둘중에 가장 큰 값을 선택해서 내려온후 마지막줄 중 가장 큰 값을 반환해주었습니다.

사실 가장 전형적이고, 다른곳에서 비슷한 문제를 풀어봤기 때문에 금방 해결하긴 했지만, 사실 제가 가장 어려워하는 알고리즘 입니다. 구조를 이해하고 점화식을 세웠을 때는 금방 문제를 풀 수있지만, 그것을 발견하지 못한다면, 가장 어려운 문제중 하나라고 생각합니다.

다양한 DP문제를 접하며 알고있는 이 알고리즘을 어떤식으로 빠르게 접목시켜야 할것 같습니다.