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

💡문제 설명 

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

 

 

정수 삼각형 

프로그래머스

---

 

👩🏻‍💻How to Solve

 

이 문제는 DP알고리즘을 이용해서 풀어야한다. 

거쳐간 숫자의 최대값을 구하는 문제인데, 자칫 생각하면 각각의 n번째 자리 수들 중에 최대값들을 뽑아내면 된다고 생각할 수도 있다. 하지만 아래로 이동할 때는 대각선 양 옆의 숫자들만 이동할 수 있으므로 성립되지 않는다. 

 

 

예시) 

먼저 첫번째 줄은 위에 줄이 없으므로 그대로 유지한다. 

 

 

두번째 줄에 있는 숫자는 3 8인데 모두 첫번째 줄 7과 연결되어 있으므로 각각 10 15로 업데이트 해준다. 

 

 

세번째 줄에 있는 숫자는 8 1 0 이다. 

잘 살펴보면 끝에 있는 숫자 8과 0은 각각 두번째 줄의 3과 8으로만 연결되어있으므로 업데이트를 고려할 때 두번째 줄의 숫자 1개만 고려하여 더해 업데이트 해주면 된다. 

하지만 세번째 줄의 가운데 숫자 1은 두번째 줄의 3과 8 모두 연결되어있다. 우리는 구할 수 있는 최대값을 구하는 것이므로 두번째 줄의 3과 8까지 업데이트된 숫자들(10 15) 의 최대값 중 1과 더하여 업데이트 해주면 된다. 

 

 

네번째 줄에 있는 숫자는 2 7 4 4이다. 

세번째 줄과 마찬가지로 네번째 줄 끝에 있는 숫자 2 4는 각각 세번째 줄의 8 0으로만 연결되어 있으므로 8과 0까지 업데이트 된 수에 각각 2와 4를 더하여 업데이트 시켜준다. 

 

나머지 가운데에 있는 값 7과 4는 각각 8과 1, 1과 0으로 연결되어 있다. 

세번째 줄에서와 마찬가지로 7과 연결된 8과 1에 업데이트 된 최대값(18 16)을 7과 더하여 업데이트를 시켜준다. 

4도 마찬가지로 연결되어있는 수  1과 0에 업데이트된 최대값(16 15) 중 7과 더하여 업데이트 시켜준다. 

 

다섯번째 줄에 있는 숫자는 4 5 2 6 5이다. 

위와 마찬가지로 다섯번째 줄도 24 30 27 26 24로 업데이트 해준다. 

 

 

💻 Code

def solution(triangle):
    for i in range(1, len(triangle)): #1번째 줄, 2번째 줄, ... , 
        for j in range(i+1): #1번째줄의 1번째 수, 2번째 줄의 1번째 수, 2번째 수, ...  
            if j == 0: #수가 0번째 자리 
                triangle[i][j] += triangle[i-1][j]
            elif j == i: #수가 가운데 
                triangle[i][j] += triangle[i-1][j-1]
            else: #수가 맨 끝 
                triangle[i][j] += max(triangle[i-1][j], triangle[i-1][j-1])
    return max(triangle[-1])