[Python] 백준 1932: 정수 삼각형

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

1932번: 정수 삼각형

ANS

N = int(input())
triangle = [list(map(int,input().split())) for _ in range(N)]

#목표는 그때그때 작은 것을 찾아서 저장해주는 것. (행+1, 열)과 (행+1, 열+1) 중에서 큰 값 찾기!
#삼각형의 제일 왼쪽과 오른쪽은 특수하게 처리해주어야 한다. max값을 사용해서 비교하지 않는다.
r = 0
c = 0
sumV = triangle[r][c]

for i in range(1,N): #행
    for j in range(len(triangle[i])): #열
        if j == 0: #맨 왼쪽에 있는 경우
            triangle[i][j] = triangle[i][j] + triangle[i-1][0]
        elif j == len(triangle[i])-1: #맨 오른쪽에 있는 경우
            triangle[i][j] = triangle[i][j] + triangle[i-1][j-1]
        else:
            triangle[i][j] = max(triangle[i][j] + triangle[i-1][j], triangle[i][j]+triangle[i-1][j-1])
print(max(triangle[N-1]))

 

TC에서 주어진 정수 삼각형을 이용해서 해당 삼각형의 행-열에는 어떠한 값을 더하게 되는지 규칙을 찾는 식으로 접근을 했다. 맨 왼쪽, 맨 오른쪽 요소는 max값으로 해당 값을 저장하지 않아도 된다는 것을 알아냈으며, 그 외의 요소들은 max값을 넣어주어야 한다는 것을 알게 되었다. 시간이 부족할 수 있기 때문에 따로 여분의 리스트를 만들지 않았고 triangle 리스트를 돌면서 값 갱신을 시켜주고자 했다. 마지막 행의 max값이 우리가 원하는 값!