프로그래머스) 정수 삼각형

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

대표적인 dp 문제인거 같다. 예전에 백준에서도 잠깐 본거 같은 문제.

소요 시간 : 20분

def solution(triangle):
    answer = 0
    size = len(triangle)
    dp = list(triangle)

    for i in range(size):
        for j in range(i+1):
            me = dp[i][j]
            left = 0
            right = 0

            if i - 1 < 0:
                left = 0
                right = 0
            else:
                if j - 1 < 0:
                    left = 0
                    right = triangle[i - 1][j]
                elif i - 1 < j :
                    left = triangle[i - 1][j - 1]
                    right = 0
                else:
                    left = triangle[i - 1][j - 1]
                    right = triangle[i - 1][j]
            dp[i][j] = max(me + left, me + right)

    answer = max(dp[size-1])
    return answer

dp는 많이 약해서 일단 생각나는데로 짰다. 경우의 수를 분류해서 문제를 풀었다. 하지만 코드 가독성은 매우 떨어지는 편이다.

다른사람 코드를 보니 동작 방식은 비슷하지만 매우 깔끔했다. 특히 왼쪽과 오른쪽 indexError가 나는 부분에 0을 추가해서 푸는 방식이 괜찮아 보였다.

dp를 선언할 필요 없이 triangle배열로 끝낼 수 있다.dp를 선언해서 공간복잡도가 좋지 않다.

# 다른 사람 정답 코드
def solution(triangle):
	answer = 0
	for i in range(1, len(triangle)):
    	for j in range(len(triangle[j])):
        if j == 0:
        	triangle[i][j] += triangle[i-1][j]
        elif j == len(triangle[i])-1:
        	triangle[i][j] += triangle[i-1][j-1]
        else:
        	triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
    answer = max(triangle[-1])
    return answer