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

 

https://programmers.co.kr/learn/courses/30/lessons/43105?language=python3

코딩테스트 연습 - 정수 삼각형

 

내가 푼 풀이 1

def solution(triangle):
    max_list=[0]*len(triangle)
    max_list[0]=triangle[0][0]
    answer = 0
    i=1
    j=0
    while i<len(triangle):
    
        max_list[i]=max_list[i-1]+max(triangle[i][j:j+2])
        j=triangle[i].index(max(triangle[i][j:j+2]))
        i+=1
    
        
    answer=max_list[-1]
   
    return answer

처음에는 그리디 알고리즘을 이용해 top-down 방식으로 코드를 짰다.

현재 칸에서 최선의 값(최대값)을 선택해야 다 더했을때 가장 큰 값이 될 것 이라 생각을 하고 푼 것 인데, 

이 문제의 경우 선택한 숫자 "전체"를 다 더 했을 때 가장 큰 값이 되어야 하기 때문에

모든 경우의 수를 다 고려해야했다.

즉, 동적 계획법으로 각각의 수를 다 고려한 다음 만들 수 있는 가장 큰 값을 선택해야한다.

 

내가 푼 풀이-2 

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