[프로그래머스/Python] 정수 삼각형 - Level3

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

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

이 문제는 동적계획법 문제로 꼭대기부터 최대값이 될 수 있도록 업데이트하며 풀어야 하는 문제였다.

양쪽 끝인 경우에는 그 전 줄의 양쪽 끝에만 영향을 받으므로 값을 비교할 필요 없이 더해주기만 하면 된다.

가운데인 경우에는 그 전 줄의 두 값에 영향을 받으므로 값을 비교하여 더 큰 값을 더해주면 된다.

 

다음 예시를 보면 이해하기 더 쉬울 것이다.

 

예시로 이런 삼각형이 있다고 하겠다.
7 3    8 8    1    0 2    7    4    4 4    5    2    6    5
2번째 줄 업데이트
7 10    15 8    1    0 2    7    4    4 4     5    2     6     5
3번째 줄 업데이트
7 10    15 18    16    15 2    7    4    4 4     5    2     6     5
4번째 줄 업데이트
7 10    15 18    16    15 20    25    20    19 4     5    2     6     5
5번째 줄 업데이트 -> 마지막 줄에서 최대값 = answer
7 10    15 18    16    15 20    25    20    19 24     30    27     26     24

 

위의 방법으로 짠 코드는 다음과 같다.

def solution(triangle):

    for i in range(1, len(triangle)): # i = 몇번째 줄인지
        for j in range(i+1): # j = 줄 안에서 인덱스
            if j == 0: # 가장 왼쪽인 경우
                triangle[i][j] += triangle[i-1][j]
            elif j == i: # 가장 오른쪽인 경우
                triangle[i][j] += triangle[i-1][-1]
            else: # 가운데인 경우
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
                
    return max(triangle[-1])

반복문을 통해 줄을 한 줄씩 옮기면서 최대값이 될 수 있도록 값들을 업데이트 해준다. 가장 왼쪽이거나 오른쪽인 경우에는 값을 비교할 필요가 없으므로 그 전 줄의 양쪽 끝 값을 더해주기만 하면 된다. 가운데인 경우 그 전 줄의 두 값을 비교해야 하므로 두 값 중 큰 값을 더해준다.

마지막 줄에서 최대값이 정답이 되므로 최대값을 리턴해준다.

 

다른 사람들의 풀이를 봤더니 접근 방법은 똑같지만 생각을 달리한 코드도 있었다. 

def solution(triangle):
    triangle = [[0] + line + [0] for line in triangle]
    
    for i in range(1, len(triangle)):
        for j in range(1, i+2):
            triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
            
    return max(triangle[-1])