[Python] 백준 1932번 - 정수 삼각형

문제

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

 

 

 

---

표준 입력을 위한 sys모듈 추가.

정수 하나 입력.

입력받은 정수 만큼 층을 갖는 삼각형(정수) 입력받아 리스트에 저장(2차원).

import sys


input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

 

 

삼각형의 맨 아래의 윗층(n-2 index)부터 탐색.

- 해당 i, j번째를 기준으로 아래에 있는 두 요소 ([i+1][j], [i+1][j+1]) 중 큰 값을 해당 번째에 누적하여 더해줌.

 

삼각형의 맨 위의 값([0][0]) 출력.

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

print(arr[0][0])

 

 

전체 코드.

import sys


input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

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

print(arr[0][0])