[백준/파이썬/DP] 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 이하이다.

 

정답

import sys
num = int(sys.stdin.readline())
arr = []

for i in range(num):
    tmp = list(map(int,sys.stdin.readline().split()))
    if len(arr)==0:
        arr = tmp
    else:
        tmp[0] = tmp[0] + arr[0]
        tmp[len(arr)] = tmp[len(arr)] + arr[len(arr)-1]
        
        for j in range(1, len(arr)):
            tmp[j] = max(tmp[j]+arr[j-1], tmp[j]+arr[j])
        arr = tmp

print(max(arr))

1. num에 값 입력, arr배열세팅

2. for문 - tmp에 리스트 입력 후 if문 - arr가 비어있을 때 tmp값 arr에 입력

3. else문 - 맨 왼쪽, 맨 오른쪽 따로 세팅

4. else문 - for문 - tmp에 왼쪽에서 더할 때랑 오른쪽에서 더할 때 값 비교 후 큰 값 입력

5. arr에 tmp값 입력

6. 마지막 arr에 최댓값 출력