[BOJ/Step15] 1932 : 정수 삼각형 (Python)

www.acmicpc.net/problem/1932

1932번: 정수 삼각형

---

1149번이랑 같은 방식으로 접근하면 된다

 

1. 입력받은 수를 피라미드 형식의 이중 리스트 tri에 저장

2. 두번째 줄부터 한줄한줄 이전 줄에 자신을 선택 가능한 두가지 수 중 더 큰 수를 자신에 더한다

  2-1. 첫번째 숫자는 이전 줄의 첫번째 숫자만이 자신을 선택할 수 있으므로 무조건 첫번째 숫자만 더해준다

  2-2. 마지막 숫자는 이전 줄의 마지막 숫자만이 자신을 선택할 수 있으므로 무조건 마지막 숫자만 더해준다

3. tri의 마지막 줄에서 가장 큰 숫자를 출력한다

 

# 1932.py

n = int(input())

tri = [[i for i in map(int, input().split())] for i in range(n)]

for i in range(1, n):
    tri[i][0] = tri[i][0] + tri[i-1][0]
    for j in range(1, i):
        tri[i][j] = tri[i][j] + max(tri[i-1][j-1], tri[i-1][j])
    tri[i][i] = tri[i][i] + tri[i-1][i-1]

print(max(tri[n-1]))