[baekjoon] 백준 1932 번 : 정수 삼각형 (by python 파이썬)

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

1932번: 정수 삼각형

 

정답 code

#정수 삼각형
import sys
input = sys.stdin.readline

n = int(input())
t = []

for _ in range(n):
    num = list(map(int,input().split()))
    t.append(num)


for i in range(1,n): # 층수 (0층은 한개의 값) 
    for j in range(i+1): #가로줄 선택 (층수+1)개만큼 존재
        # 가장 왼쪽 값일때 위의 값
        if j == 0:
            t[i][j] = t[i][j] + t[i-1][j]
        # 가장 오른쪽 값일때 좌측 위의 값
        elif i == j:
            t[i][j] = t[i][j] + t[i-1][j-1]
        # 나머지의 경우 좌측 위와 우측 위중 큰 값
        else:
            t[i][j] = max(t[i-1][j-1],t[i-1][j]) + t[i][j]
        
print(max(t[n-1]))

 

solution

처음에 이 문제를 보고 하나씩 내려오면서 찾으면 시간초과가 발생할거라 생각 했지만 이 방법이 맞았다.

 

이중 for문으로 i는 층수를 j는 그 층에 있는 요소들을 방문하며 최대 값을 저장해나가면된다.

생각해야될것은

1. 가장 왼쪽에 있는 요소는 바로위의 요소를 가져옴

2. 가장 오른쪽에 있는 요소는 왼쪽 위에 요소를 가져옴

3. 중앙에 값들은 좌측위, 우측위 중 최대값을 가져오면 된다.