[백준 1932번] 파이썬 - 정수 삼각형

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

1932번: 정수 삼각형

 

 

 

# 조건

 

• 위 그림은 크기가 5인 정수 삼각형
• 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하여라
• 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택 가능하다.
• 삼각형의 크기는 1 이상 500이하

 

# 접근 방법

• DP를 이용하여 각 수에 누적합을 구해주고 가장 큰 수를 출력해주면 된다.
• 입력을 층마다 받기 때문에 2차원 리스트를 사용한다
• 따라서, 아래 층에 더해줄 수 있는 위층의 인덱스는 아래층 인덱스 -1 또는 아래층과 동일 인덱스이다.
  • 2개의 위층에서 더해줄 수 있는 경우는 max를 이용하여 비교해준다..
• 인덱스에러 방지를 위해 조건문을 잘 달아주면 될 것같다.
  • 한 층씩 내려올 때마다 길이는 +1씩 되므로, 처음과 마지막 인덱스에서만 조건문을 잘 달아주자.
• 2중 반복문을 돌리는데, 큰 반복문의 경우 -> 층을 표현
• 내부 반복문인 경우 -> 층에 가질수 있는 숫자의 개수를 표현한다.
  • 층 + 1개의 수를 가질 수 있으며 인덱스는 0~층의 수와 같다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from copy import deepcopy  
  
N = int(input())  
  
triangle = [[*map(int, input().split())] for _ in range(N)]  
  
# 삼각형 크기가 1인경우 바로 출력  
if len(triangle) == 1:  
    print(*triangle[0])  
else:  
    # 가장 위층 = 0층으로 생각  
    # 1층부터 제일 아랫층 까지    
    for i in range(1, N):  
        # 0~현재 층까지의 인덱스를 가지고 있음  
        for j in range(i+1):  
            # 시작과 끝이 아니라면 위층의 두 수 중 더 큰 값을 선택  
            if not j == 0 and not j == i:  
                triangle[i][j] = max(triangle[i-1][j-1]+triangle[i][j], triangle[i-1][j] + triangle[i][j])  
            elif j == 0:  
                triangle[i][j] = triangle[i-1][j] + triangle[i][j]  
  
            elif j == i:  
                triangle[i][j] = triangle[i-1][j-1] + triangle[i][j]  
  
    print(max(triangle[-1]))