프로그래머스 정수 삼각형

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

문제 설명

문제풀이 

• DP 문제로 현재 위치에 가장 max 값을 넣어서 가장 마지막 줄에 max값을 구하면 되는 문제였다.
• 아이디어는 금방 떠올랐으나 if문을 더 적게 사용하는 방법을 고민하다 보니 시간이 좀 더 걸렸다.(결국 처음 생각한대로 작성함)

def solution(triangle):
    lst = []
    
    for layer in triangle:
        if len(layer)== 1 : 
            lst.append(layer)
            continue
        max_len = len(layer)
        temp = []
        for i in range(max_len):
            if i == 0:
                temp.append(lst[-1][i] + layer[i])
            elif i == max_len-1:
                temp.append(lst[-1][i-1] + layer[i])
            else: temp.append(max(lst[-1][i] ,lst[-1][i-1]) +layer[i])    
        lst.append(temp)   
    return max(lst[-1])

다른 사람의 풀이

• triangle을 저장하는 매개체로 사용하여 더 적은 메모리를 사용한 코드임을 알 수 있음.

def solution(triangle):
    dp = []
    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])