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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

문제를 간단히 요약하자면 다음과 같다.

정삼각형 형태의 피라미드에 숫자가 주어진다.

젤 위의 꼭지점에서 출발하여 바닥으로 이동한다고 할 때, 왼쪽 아래나 오른쪽 아래로만 움직일 수 있다.

이 때, 이동하면서 얻을 수 있는 숫자 합의 최댓값은 얼마인지 반환해야한다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. 이동할 수 있는 경우의 수가 두 가지 밖에 없으므로 더했을 때, 둘 중에 더 큰 값을 이동경로로 선택하여, 합한 값을 피라미드에 다시 대입한다.

2. 바닥까지 계속 반복하면 마지막 바닥의 열에는 최종 합이 있을 것이다.

3. 이중에서 최댓값을 반환한다.

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j==0: #2번 : j가 0일 경우에는 움직일 수 있는 경우가 위에서 왼쪽 아래로 내려오는 경우 밖에 없다.
                triangle[i][j]+=triangle[i-1][j] #따라서, 경우가 하나이기에 최댓값을 구할 필요가 없다.
            elif j==i: #2번 : j와 i가 같은 경우에는 움직일 수 있는 경우가 위에서 오른쪽 아래로 내려오는 경우 밖에 없다.
                triangle[i][j]+=triangle[i-1][j-1]
            else: #2번 : 나머지로 움직일 수 있는 경우의 수가 두 가지인 경우이다.
                triangle[i][j]+=max(triangle[i-1][j],triangle[i-1][j-1])
    return max(triangle[-1])

처음에는 DFS 알고리즘을 사용하여, 꼭대기에서 바닥까지의 합을 구한 뒤, 최댓값을 구하는 방법을 사용하였다.

하지만, 문제 해결적인 측면에서는 해당 방법이 조금 더 매력적인 코드라고 생각하였다.

간결하고 보기 쉬운 코드를 작성하는 것은 좋은 개발자가 되기 위한 필수 요소라고 생각한다.