문제 링크

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

문제

분류

• 알고리즘 분류
  동적계획법, Dynamic Programming

• 난이도
  프로그래머스 Level 3

• 사용 언어
  python 3

코드

try 1

전체 탐색, 재귀 호출

모든 경우의 수를 조사하는 전체 탐색을
트리 구조를 모방한 재귀 호출로 시도

def solution(triangle):
    answer = returnMax(triangle, 0, 0, 0)
    return answer


def returnMax(arr, indexY, indexX, sum):
    sum += arr[indexY][indexX]
    
    if(indexY == len(arr)-1): # 삼각형의 밑변인 경우 종료
        return sum
    
    # 삼각형의 그림 중 왼쪽 아래, 오른쪽 아래의 경로를 통했을 경우
    # 각각의 값들을 재귀호출로 탐색
    return max(returnMax(arr, indexY+1, indexX, sum),
               returnMax(arr, indexY+1, indexX+1, sum))

결과

문제의 의도는 맞으나 효율이 너무 낮음

패인

전체 탐색으로 모든 경우의 수를 포함하니 중복 계산이 많이 들어감
또한 분류가 DP인데 메모이제이션은 하나도 하지 않았음을 깨닫고 처음부터 다시 시도함

try 2

동적 계획법

삼각형의 한 층씩 내려가면서
각 노드가 받을 수 있는 최댓값을 저장해 놓으면서 내려감

triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
부분과 같이 해당 노드는 바로 위 두 개의 노드 중 큰 값을 더해서 저장

def solution(triangle):
    answer = 0
    
    for i in range(1, len(triangle)): # 루트 제외
        for j in range(len(triangle[i])):
            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

결과

백점이다 :)

마치며

코테 연습을 거의 안해봤어서 많이 헤맸다.(사실 엉뚱한 3번 정도의 시도가 더 있었다)
또한 코드 구성이 눈에 잘 들어오질 않는다. 이것은 추후에 보완 하도록 해야겠다.