[코딩테스트] 프로그래머스 정수 삼각형 파이썬(Python)

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

프로그래머스

def solution(triangle):   
    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:
                cur_num= triangle[i][j]
                triangle[i][j] = max(cur_num + triangle[i-1][j-1], cur_num+triangle[i-1][j])

    return max(triangle[-1])

예제를 통하여 문제풀이 방법에 대해서 이야기하겠습니다.

예제는 문제에서 주어진 예제와 동일하며 각 숫자의 인덱스를 포함하여 표현했습니다.

저는 일정한 규칙을 찾아내어서 문제를 해결할 수 있었습니다.

규칙은 아래와 같습니다.

1. 규칙 1 : 왼쪽 가장자리 숫자는 이전 줄의 왼쪽 가장자리 숫자와 더하여 저장한다.
2. 규칙 2 : 오른쪽 가장자리 숫자는 이전 줄의 오른쪽 가장자리 숫자와 더하여 저장한다.
3. 규칙 3 : 규칙1,2에 해당하지 않는 위치라면 이전 줄의 왼쪽, 오른쪽 경로의 값을 더했을 경우 더 큰 값을 저장한다.

먼저 규칙 1, 2번을 적용하면 아래와 같은 삼각형이 됩니다.

먼저 규칙1 을 작성해보면 아래와 같습니다.

[1][0] = [1][0] + [0][0]

[2][0] = [2][0] + [1][0]

[3][0] = [3][0] + [2][0]

[4][0] = [4][0] + [3][0]

정리하면

[i][j] = [i][j] + [i-1][j] 와 같습니다.

 

규칙 2는 아래와 같습니다.

[1][1] = [1][1] + [0][0]

[2][2] = [2][2] + [1][1]

[3][3] = [3][3] + [2][2]

[4][4] = [4][4] + [3][3]

정리하면

[i][j] =[i][j] + [i-1][j-1] 과 같습니다.

 

다음은 규칙 3을 적용해보겠습니다.

[2][1] = max([2][1]+[1][0], [2][1]+[1][1])

[3][1] = max([3][1]+[2][0], [3][1] +[2][1])

[3][2] = max([3][2]+[2][1], [3][2]+[2][2])

...

[i][j] = max([i][j]+[i-1][j-1], [i][j]+[i-1][j])

 

 

이렇게 만든 규칙을 코드로 적용하고 계산하고 나온 triangle의 가장 마지막 줄의 max()를 취하여 결과로 반환하면 문제를 해결할 수 있습니다.