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

문제 정보

• 프로그래머스 문제 링크
• 난이도 : level 3

 

해결 방법

1. 문제에 명시된 대로 거쳐간 숫자의 합이 가장 큰 경우를 찾기 위해 Top-down 방식의 DP 를 사용하여 구현했습니다. 제출하니 시간이 많이 초과되어 다른 방법의 풀이를 시도했습니다.

2. 모든 경로를 반복해서 수행하지 않도록 특정 경로까지의 최대 값을 triangle 배열에 update 했습니다. 짧은 경로는 금방 구할 수 있기 때문에 Bottom-up 방식으로 구현했습니다.

 

소스 코드

# 시간초과
def solution(triangle):
    answer = 0
    answerList = []
    
    def dp(depth, curSum, idx):
        curNum = triangle[depth - 1][idx]
        curSum += curNum
        
        #print('depth - 1:' + str(depth - 1) + ' / idx:' + str(idx) + ' / curSum:' + str(curSum))
        
        if(len(triangle) <= depth):
            answerList.append(curSum)    
            return
        
        dp(depth + 1, curSum, idx)
        dp(depth + 1, curSum, idx + 1)
        
    dp(1, 0, 0)
    
    answer = max(answerList)
       
    return answer

def solution(triangle):
    answer = 0
    depth = 1 # triangle[depth]
    
    # 현재 depth 에 있는 숫자의 합을 이전 depth 에서 가져옴
    while depth < len(triangle):
        for idx in range(0, depth + 1):
            addNum = 0
            if(idx == 0):
                addNum = triangle[depth - 1][idx]
            elif(idx == depth):
                addNum = triangle[depth - 1][idx - 1]
            else:
                addNum = max(triangle[depth - 1][idx - 1], triangle[depth - 1][idx])
            
            # 다음 줄에 합산    
            #print('addNum:' + str(addNum) + ' / depth:' + str(depth) + ' / idx:' + str(idx))
            triangle[depth][idx] += addNum
        
        #for idx in range(0, depth + 1):
        #    print(str(triangle[idx]))
            
        depth += 1
    
    answer = max(triangle[len(triangle) - 1])
    return answer

처음 구현할 때는 depth 를 1 부터 시작하도록 하였으나 두번 째 구현시부터 인덱스 가 직관적으로 보이지 않아서 depth 를 0 부터 시작하도록 수정했습니다.

 

생각해볼 문제

• 두 번째 방식으로 구현한 것은 프로그래머스 문제 유형에 명시된 DP (동적계획법) 으로 풀이하지 않았는데 시간 초과없이 풀이 할 수 있는 방법을 추가로 확인해 봐야할 것 같습니다.

 

참고 자료

• [자료구조와 알고리즘] 동적 계획법(Dynamic Programming, DP)