[프로그래머스] 정수 삼각형

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

 

 

 

def solution(triangle):
    answer = triangle[0][0]
    if len(triangle) == 1:
        return answer
    d = [[0] * (i + 1) for i in range(len(triangle))]
    d[0][0] = triangle[0][0]
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0: # 삼각형 i열 0번째
                d[i][j] = d[i-1][j] + triangle[i][j];
            elif j == i: # 삼각형 i열 마지막
                d[i][j] = d[i-1][j-1] + triangle[i][j];
            else:
                d[i][j] = max(d[i-1][j-1], d[i-1][j]) + triangle[i][j];
            answer = max(answer, d[i][j]);
    return answer

 

 

 

 

** 추천 많이 받은 것 중에 제일 좋았던 풀이

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

 

방식은 똑같은데 1) 더 간결하고 2) 내 식보다 효율적이고 3) 이게 dp에 맞아서 가져옴