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

 

 

문제

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

 

 

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제다.

 

아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다.

 

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 숫자의 합의 가장 큰 경우를 return하는 문제다.

 

 

제한

 

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

 

 

입력, 출력 예시

 

 

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

 

 

 

풀이

 

 

이 문제는 바닥까지 내려왔을 때 가장 큰 숫자를 찾는 문제다.

 

일일히 모든 경우를 계산하면 경우의 수가 너무 많아 오래 걸리기 때문에 한 층씩 내려올 때마다 값들을 누적해서 최댓값들을 해당하는 층의 칸에 저장해 둔다.

 

그러면 n번째 층의 최댓값들을 구하기 위해서는 n-1번째 층에 있는 칸에서 n번째 층의 숫자들을 더해서 각 칸에 올 수 있는 최댓값을 비교하면 된다.

​

 

 

그림에서 볼 수 있듯이 7부터 시작하면 2층에는 첫번째 칸에는 3, 두번째 칸에는 8을 더한 10과 15를 저장한다.

 

그리고 3층의 첫번째 칸에는 10에서 8을 더한 18, 두번째 칸에는 10에서 1을 더한 11과 15에서 1을 더한 16을 비교하고 더 큰 16을 저장한다.(3층의 두번째 칸을 지날때 16보다 더 큰 수가 저장되는 경우는 없다.) 마지막으로 3층의 3번째 칸에는 15에 0을 더한 15를 저장한다.

 

이런 식으로 행렬을 채워나가면 마지막 층의 칸에 저장된 수 중 최댓값을 구하면 된다.

​

[요약]

 

각 층의 칸에 왔을 때 나올 수 있는 값의 최댓값을 이용해 다음 층을 계산하면, 그 칸을 지나서 내려가는 경우 중 최댓값 보다 더 큰 값이 없기 때문에 무조건 그 칸을 지나는 경우 중 최댓값이 최종적으로 저장된다.

 

 

Code

 

 

def solution(triangle):
    lst_len=len(triangle)
    lst=[[0]*(lst_len+1) for _ in range(lst_len+1)]
    lst[1][1]=triangle[0][0]
    for i in range(1,lst_len+1):
        for j in range(1,i+1):
            lst[i][j]=max(lst[i-1][j-1],lst[i-1][j])+triangle[i-1][j-1]
    answer=max(lst[lst_len])
    return answer

 

---

 

생각보다 설명 요약이 훨씬 어렵...

 

프로그래머스