[이코테] 정수 삼각형(Python) / 백준 1932

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

 

 

 

 

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

 

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

 

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

 

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

 

예제 입력1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

 

 

예제 출력1

30

 

 

나의 풀이

이번 문제는 예전에 프로그래머스에서 비슷한 문제가 있어 그때의 기억을 더듬어서 접근했다.

처음에 문제를 봤을 땐, 이 방향으로 갔다가 저 방향으로 가면 어떻게 다시 계산하고, 되돌 오지?라고 생각이 들었는데

이번 문제가 DP이고 나름의 규칙을 찾는다는 마음으로 접근하니 스스로 풀 수 있었다.

위의 과정을 보며 우리는 양쪽 사이드라인은 왼쪽은 (i-1, j)만 오른쪽은 (i-1, j-1)만 더해가고

안쪽에 있는 수들은 자신의 왼쪽 위 대각선, 오른쪽 위 대각선의 값과 자기 자신과 더해 둘 중 큰 값이 현재 위치의 값이 되는 것이다. 아래 그림은 이에 대한 풀이 그림이다.

최댓값 구하는 과정

마지막 줄에서 최댓값을 찾으면 된다.

 

## 백준 1932 :  정수 삼각형
import sys
input = sys.stdin.readline

n = int(input())
#arr = [[0]*n for _ in range(n)]
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
        

for i in range(1, n):
    for j in range(len(arr[i])):
        if  j == 0: 	## 왼쪽라인
            arr[i][j] += arr[i-1][j]
           
        elif  j == len(arr[i])-1:	## 오른쪽 라인
            arr[i][j] += arr[i-1][j-1]
            
        else: 		## 그외
##        elif 0 < j < len(arr[i]):
            arr[i][j] += max(arr[i-1][j-1], arr[i-1][j])



##print(max(map(max, arr)))
print(max(arr[n-1]))    ## 마지막행에서(n-1) 최댓값 출력