[lv3] 1932. 정수 삼각형(Python 파이썬 풀이)

출처

https://www.acmicpc.net/problem/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번째 줄까지 정수 삼각형이 주어진다.

출력

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

예제 입력

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

예제 출력

30

해석

입력값에서 두번 째 줄부터는 li값이라고 2차 리스트에 저장해 두고, for 구문을 통하여 단계가 내려갈 때마다 위의 값들 중 최댓값을 골라서 이전 값에서 더해주는 형식으로 풀면 됩니다. 만약 인덱스가 값이 0이거나 끝에 있는 경우에는 이전의 끝자리에 있던 값을 그대로 받는 조건을 넣어주면 됩니다. 그리고 마지막 줄에서 최댓값을 출력해주면 됩니다.

소스 코드

1 2 3 4 5 6 7 8 9 10 11 12 13

import sys   n = int(sys.stdin.readline()) li = list(list(map(int,sys.stdin.readline().strip().split())) for _ in range(n)) for i in range(1, n):     for j in range(len(li[i])):         if j == 0:             li[i][j] += li[i-1][j]         elif j == len(li[i]) - 1:             li[i][j] += li[i-1][j-1]         else:             li[i][j] += max(li[i-1][j-1], li[i-1][j]) print(max(li[-1])) Colored by Color Scripter

cs