프로그래머스 정수 삼각형 코드 및 해설 (파이썬)

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

코딩테스트 연습 - 정수 삼각형

 

💡 Dynamic Programming으로 풀이했습니다. 

 

먼저 주어진 triangle과 같은 shape의 dp라는 리스트를 생성합니다. 이때 모든 값은 0으로 초기화합니다. 

dp의 두 번째 줄부터, 각 위치에 도달할 때까지의 최댓값을 dp에 저장합니다. 

cf. dp의 첫 번째 줄에선 아직까지 더해온 값이 없어 그대로 0이므로 고려하지 않아도 됩니다. 

dp의 마지막 줄에 다다를 때까지 이를 반복하고, 마지막 줄에 도달하면 while문을 종료합니다.

 

여기까지 실행하면 dp의 마지막 줄엔 triangle의 마지막 줄의 각 위치에 도달할 때까지의 최댓값이 저장되어 있습니다. 이 값들을 각각 triangle의 위치에 해당하는 값과 더해주면, 각 위치에서 가능한 최종적인 합의 최댓값을 구할 수 있습니다. 이 리스트의 최댓값을 반환하면 정답을 얻을 수 있습니다. 

 

def solution(triangle):
    N = len(triangle)
    # triangle과 같은 shape의 0으로 초기화된 list 
    dp = [[0]*i for i in range(1,N+1)]
    depth = 1
    
    # dp를 각 위치에서 가능한 최댓값으로 채우기 
    while depth < len(triangle):
        for idx, val in enumerate(triangle[depth]):
            # idx == 0인 경우, 윗 줄의 0번째 값만 접근 가능 
            if idx == 0:
                dp[depth][idx] = dp[depth-1][idx] + triangle[depth-1][idx]
            # idx == depth인 경우(해당 줄의 마지막 값인 경우), 윗 줄의 마지막 값만 접근 가능 
            elif idx == depth:
                dp[depth][idx] = dp[depth-1][idx-1] + triangle[depth-1][idx-1]
            # 0 < idx and idx < depth인 경우, 윗 줄에서 자신과 index가 같은 값과 자신보다 index가 1만큼 작은 값에 접근 가능 
            else: 
                dp[depth][idx] = max(dp[depth-1][idx] + triangle[depth-1][idx], dp[depth-1][idx-1] + triangle[depth-1][idx-1])

        depth += 1
    
    # dp의 마지막 줄의 값들을 각각 해당하는 triangle의 값과 더해 최댓값을 반환 
    return max([a+b for a,b in zip(dp[-1], triangle[-1])])
    

 

 

 

cf. Dynamic Programming을 사용하지 않고 그냥 모든 가능한 방법에 대해 합을 구해 리스트에 저장하고, 이 리스트에서 최댓값을 구하는 방식을 다음과 같다. 이렇게 하면 (당연히) 시간 초과로 통과가 안 된다.. 

 

def solution(triangle):
    # 모든 가능한 방법의 합을 저장할 리스트 
    sums = []

    def search(root_pos, sum_, depth):
        # 마지막 줄까지 다 더했으면 빠져나오기 
        if depth == len(triangle):
            sums.append(sum_)
            return 

        x, y = root_pos
        # root는 다음 줄에서 자신과 index가 같거나, 자신의 index보다 1만큼 큰 값에 접근할 수 있다 
        children = [[x+1, y], [x+1, y+1]]
        for child in children:
            # root_pos는 현재 위치인 child로, sum_은 현재 root의 값을 더한 겂으로, depth는 1만큼 증가한 값으로 준다 
            search(child, sum_ + triangle[x][y], depth +1)
            
    # recursive search를 시작한다 
    search([0,0], sum_=0, depth=0)
    
    # 가능한 모든 합 중 최댓값을 반환한다 
    return max(sums)